在网站上做广告,如何做摄影网站,南翔做网站公司,网站开发环境介绍1、数论 1质数判定 in/i优化O(sqrt(n))
bool is_prime(int n){if(n2)return false;for(int i2;in/i;i){if(n%i0)return false;} true;
} 分解质因数 in/i优化O(sqrt(n))
// 定义一个函数 divide#xff0c;接收一个整数 n 作为参数#xff0c;用于分解质…1、数论 1质数判定 in/i优化O(sqrt(n))
bool is_prime(int n){if(n2)return false;for(int i2;in/i;i){if(n%i0)return false;} true;
} 分解质因数 in/i优化O(sqrt(n))
// 定义一个函数 divide接收一个整数 n 作为参数用于分解质因数
void divide(int n){// 使用一个循环从2开始遍历到sqrt(n)即n/i因为一个// 大于sqrt(n)的因数必定和一个小于或等于sqrt(n)的因数成对出现for(int i2;in/i;i){// 如果 n 能被 i 整除说明 i 是 n 的一个因数if(n%i0){int s0; // 定义一个计数器 s用于记录当前因数 i 的个数// 使用一个内层循环持续除以当前的因数 i直到 n 不能被 i 整除为止while(n%i0){n/i; // 将 n 除以当前的因数 is; // 计数器 s 自增记录当前因数 i 的个数}// 输出当前的因数 i 和它的个数 scouti sendl;}}// 循环结束后如果 n 大于 1说明 n 本身就是一个质数并且是 n 的一个因数if(n1)coutn 1endl; // 输出 n 本身作为质因数个数为 1
} 埃氏筛法一个数P中的1到P-1中的质数不是P的因数P就是质因数 欧式筛法n只会被最小质因子筛掉。
int primes[N],cnt;
bool st[N];
void get_primes(int n){//埃氏筛法 O(nloglogn)for(int i2;in;i){if(!st[i]){primes[cnt]i;for(int jii;jn;ji)st[j]true;}}
}
void get_primes(int n){//欧式筛法 for(int i2;in;i){if(!st[i])primes[cnt]i;for(int j0;primes[j]n/i;j){从小到大枚举质数st[primes[j]*i]true;//用最小质因子数把倍数筛掉if(i%primes[j]0)break;//prime[j]一定是i的最小质因子 //i%pj0时pj一定是i的最小质因子,pj一定是pj*i的最小质因子//i%pj!0时pj一定小于i的所有质因子,pj也一定是pj*i的最小质因子//对于一个合数x假设pj是x的最小质因子当i枚举到x/pj时都会筛掉 //每一个数都有一个最小质因子,都只会被筛一次所以是线性的 } }
} 2约数(1)试除法求约数O(sqrt(n))
vectorintget_divisors(int n){vectorintres;for(int i1;in/i;i){if(n%i0){res.push_back(i);if(i!n/i)res.push_back(n/i);}}sort(res.begin(),res.end());return res;
} (2)约数个数
任何一个整数n因式分解后Np1^a1×p2^a2×......pk^ak那么约数个数为(a11)(a21)......(ak1)
任何一个整数n的约数dp1^b1×p2^b2×......pk^bk0biai所以每一个bi就有ai1种
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long LL;
const int mod 1e9 7;
int main() {int n;cin n;unordered_mapint, int primes;//定义一个无序映射 primes用于存储质因数及其出现的次数while (n--) {int x;cin x;for (int i 2; i x / i; i) {while (x % i 0) { // 如果 i 是 x 的一个质因数x / i; // 将 x 除以 i去除这个质因数primes[i]; // 在 primes 中增加质因数 i 的计数}}// 循环结束后如果 x 大于 1那么 x 必然是一个质数且之前没有被完全除尽if (x 1) primes[x]; // 在 primes 中增加这个质因数的计数}LL res 1;// 遍历 primes 中的每个质因数及其计数for (auto prime : primes) res res * (prime.second 1) % mod;cout res endl;return 0;
} (3)约数之和
约数之和为(p1^0p1^1......p1^k)×(p2^0p2^1......p2^k)×......(pk^0pk^1......pk^k)排列组合
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long LL;
const int mod1e97;
int main(){int n;cinn;unordered_mapint,intprimes;whlie(n--){int x;cinx;for(int i2;ix/i;i){while(x%i0){x/i;primes[i];}}if(x1)primes[x];}LL res1;for(auto prime:primes){int pprime.first,aprime.second;//底数和指数LL t1;whlie(a--)t(t*p1)%mod;resres*t%mod; }coutresendl;return 0;
} 4欧几里得算法辗转相除法求最大公约数 性质d/a d/b---d/(axby) 原理a和b的最大公约数b和a模b的最大公约数
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
