四、AcWing算法基础课

1. 求质数#includeiostream using namespace std; int main(){ int n;cinn; while(n--){ //coutnendl; int flag1; int x;cinx; if(x2){flag0;}//1不是质数 else{ for(int i2;i x/i;i){//i x/i指的就是取sqrt(x) if(x%i0){flag0;break;} } } if(flag1) coutYesendl; else coutNoendl; } return 0; }#includeiostream using namespace std; void zhishu(int x){ int yx; for(int i2;ix/i;i){ int cnt0; while(y%i0){ cnt; yy/i; } if(cnt) couti cntendl; } if (y 1) cout y 1 endl; } int main(){ int n;cinn; while(n--){ int x;cinx; zhishu(x); coutendl; } return 0; }线性筛选法内层循环用当前的primes[j]与i相乘筛掉合数并且保证每个合数只被它的最小质因子筛掉一次。#includeiostream using namespace std; const int N1e610; int st[N],prime[N];//st标记是不是合数prime标记以及筛选出来的质数 int idx; int main(){ int n;cinn; for(int i2;in;i){ if(!st[i]) prime[idx]i; for(int j0;prime[j] n / i;j){ st[prime[j]*i]1; if(i%prime[j]0) break;//内层循环用当前的primes[j]与i相乘筛掉合数并且保证每个合数只被它的最小质因子筛掉一次。 } } coutidx; return 0; }2. 约数#includeiostream #includevector #includealgorithm//sort using namespace std; vectorint v; void yueshu(int x){ for(int i1;ix/i;i){ if(x%i0){ v.push_back(i); if(x/i!i) v.push_back(x/i); } } sort(v.begin(),v.end()); } int main(){ int n;cinn; while(n--){ int x;cinx; yueshu(x); for(auto vv:v){ coutvv ; } coutendl; v.clear(); } return 0; }个数#includeiostream #includeunordered_map #includealgorithm using namespace std; const int mod 1e9 7; unordered_mapint,int mp; int main(){ int n;cinn; while(n--){ int x;cinx;int yx; for(int i2;iy/i;i){ while(x%i0){ mp[i]; x/i; } } if(x1) mp[x]; } long long res1; for(auto p:mp){ resres*(p.second1)%mod; } coutres; return 0; }之和#includeiostream #includeunordered_map #includealgorithm using namespace std; const int mod1e97; unordered_mapint,int mp; typedef long long LL; int main(){ int n;cinn; while(n--){ int x;cinx;int yx; for(int i2;iy/i;i){ while(x%i0){ mp[i]; x/i; } } if(x1) mp[x]; } long long res1; for(auto p:mp){ LL a p.first, b p.second; LL t 1; while (b -- ) t (t * a 1) % mod; res res * t % mod; } coutres; return 0; }求两个数的最大公约数#includebits/stdc.h using namespace std; int n,a,b; int gcd(int x,int y){ if(x % y 0)return y; return gcd(y,x % y); } int main() { cin n; while(n--){ cin a b; cout gcd(a,b) endl; } return 0; }4. 快速幂int的范围−2^31−2^31 -差不多2.1e9——超过就写long longlong long qmi(long long a, long long b, long long mod) {long long res 1; // 结果初始为1while (b) { // 当指数b还没处理完if (b 1) { // 如果b的当前最低位是1res res * a % mod; // 就把当前的a乘进结果}a a * a % mod; // a自身平方a - a² - a⁴ - a⁸ ...b 1; // b右移一位丢弃最低位}return res;}#includeiostream using namespace std; long long qui(long long a,long long b,long long c){ long long res1; while(b){ if((b1)){ res(res*a)%c; } a a * a%c;//不然会溢出int//a必须long long不然一乘以就超过了 bb/2; } return res; } int main(){ int n;cinn; while(n--){ long long a,b,p;cinabp; coutqui(a,b,p)endl; } return 0; }