约数个数
求约数个数可以先分解质因式
int整数范围内，约数最多的数最多有1600个，所以暴力搜索是没事的
1.轻拍牛头
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
题意就是问：全部数中除自己外有多少个因数，重复也算
则我们可以用小的因数更新大的
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int cnt[N],a[N],s[N];//cnt记录每个数的次数，s是个因数的和 int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); cnt[a[i]]++; } for(int i=1;i<N;i++)//枚举所有数 for(int j=i;j<N;j+=i)//枚举他的倍数 s[j]+=cnt[i];//这个数加上这个因数的个数 for(int i=1;i<=n;i++) printf("%d\n",s[a[i]]-1);//输出答案，因为自己不算在里面则减一 return 0; }
2.樱花
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
因为x>0并且是整数，则y-n!>0并且n!^2整除y-n!,则相当于问n!^2的约数个数都对应一个y跟x，约数就整除嘛，所以直接求n!^2的不同约数个数即可
约数个数就是（2c1+1）(2c2+1)...(2ck+1)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10,mod=1e9+7; int prime[N],cnt; bool st[N]; void init(int n)//筛质数 { for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i; for(int j=0;prime[j]*i<=n;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { int n; cin>>n; init(n); int res=1; for(int i=0;i<cnt;i++)//枚举质数 { int p=prime[i]; int s=0; for(int j=n;j;j/=p) s+=j/p;//求p的次方 res=(ll)res*(2*s+1)%mod;//答案乘上个数 } cout<<res<<endl; return 0; }
3.反素数
相当于求小于n中约数最多的数的最小数，因为不同的质数最多有9个，因为2*3*5*7*11*13*17*19*23*29>2e9,所以只需前9个不同质数即可构成所有的约数
然后2^31>2e9，所以最多枚举到30次方即可，用dfs暴搜来求
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10,mod=1e9+7; int prime[9]={2,3,5,7,11,13,17,19,23}; int maxd,number; int n; void dfs(int u,int last,int p,int s)//u是当前的质数，last是当前的次方，p是当前的数，s是当前的数的约数个数 { if(s>maxd||s==maxd&&p<number)//假如有大于当前约数的约数，或者约数数相等但是数比较小的更新一下 { maxd=s; number=p; } if(u==9) return;//假如枚举完所有质数 for(int i=1;i<=last;i++)//枚举所有次方 { if((ll)p*prime[u]>n) break;//假如大于n则不用操作了，直接跳出 p*=prime[u];//更新一下p dfs(u+1,i,p,s*(i+1));//递归下一个的质数，求约数的公式(约数变成了s*(i+1)) } } int main() { cin>>n; dfs(0,30,1,1);//暴搜来求约数最多的数的最小数 cout<<number<<endl; return 0; }
4.Hankson的趣味题
因为d是[x,c]的最小公倍数，所以枚举所有d的约数来判断符不符合[x,a]的最大公约数是b,[x,c]的最小公倍数是d，假如满足就res++;
枚举约数的个数可以先分解质因数，在dfs暴搜求每个约数即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int prime[N],cnt; bool st[N]; int a,b,c,d; int fcnt; struct { int p,s; }f[1601];//存质因数跟次幂 int divide[1601],dcnt;//存约数 int gcd(int a,int b)//求最大公约数 { return b?gcd(b,a%b):a; } void dfs(int u,int p)//枚举到第u个 当前的约数是p { if(u==fcnt)//假如枚举完了，这是个合法的约数 { divide[dcnt++]=p; return; } for(int i=0;i<=f[u].s;i++)//枚举所有次幂 { dfs(u+1,p); p*=f[u].p;//更新一下p } } void init(int n)//线性筛 { for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i; for(int j=0;prime[j]*i<=n;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } void solve() { fcnt=dcnt=0; int res=0; cin>>a>>b>>c>>d; int t=d; //将d进行分解质因式 for(int i=0;prime[i]<=t/prime[i];i++)//枚举所有质因子 { int p=prime[i]; if(t%p==0) { int s=0; while(t%p==0) t/=p,s++; f[fcnt++]={p,s};//记录这个质因数跟幂次 } } if(t>1) f[fcnt++]={t,1};//假如有剩余，也存起来 dfs(0,1);//暴力搜索所有约数 for(int i=0;i<dcnt;i++)//枚举d的所有约数 { int x=divide[i]; if(gcd(a,x)==b&&(ll)c*x/gcd(x,c)==d) res++;//假如满足条件则答案++ } cout<<res<<endl; } int main() { init(100000);//预处理出来质数 int T; cin>>T; while(T--) solve(); return 0; }
欧拉函数
欧拉函数：1~i中与i互质的数
欧拉筛模板
void init(int n)//欧拉筛 { phi[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; pri[i]=i-1; } for(int j=0;prime[j]*i<=n;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } }
1.可见的点
假如[x,y]x与y不互质，则必能约成最简【x/d,y/d】所以[x,y]这个点会被[x/d,y/d]
这个点挡住，所以只要求与x互质的y的个数加起来就是答案了，因为两边互质的数关于y=x对称，则只需y=x下面的互质数在×2就为答案，因为y=x也有一条则最终的答案+1
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int prime[N],cnt; bool st[N]; int phi[N]; void init(int n)//欧拉筛 { phi[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; phi[i]=i-1; } for(int j=0;prime[j]*i<=n;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } int main() { init(1010);//预处理出来欧拉函数 int T; cin>>T; for(int i=1;i<=T;i++) { int n,res=0; cin>>n; for(int i=1;i<=n;i++) res+=2*phi[i];//求答案 printf("%d %d %d\n",i,n,res+1); } return 0; }
2. 最大公约数
gcd（a,b）=素数d，则gcd(a/d,b/d)=1,则a/d,b/d互质，枚举质数d然后加上1~n/d的欧拉数即为答案
x，y属于（1~n/d）则映射到二维坐标就跟上一题的求法一样了，就问1~n/d之间的互质数对个数，所以提前预处理出来前缀和即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+10; int prime[N],cnt; bool st[N]; int phi[N]; ll s[N];//记录欧拉函数的前缀和 void init(int n)//欧拉筛 { phi[1]=0;//1与0互质，但是0不算在里面，则初始化为0 for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; phi[i]=i-1; } for(int j=0;prime[j]*i<=n;j++) { st[prime[j]*i]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } phi[1]=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];//处理出来欧拉数的前缀和 } int main() { int n; ll res=0; cin>>n; init(n);//欧拉筛 for(int i=0;i<cnt;i++)//枚举所有的质数d { int d=prime[i]; res+=s[n/d]*2+1;//答案加上n/d的互质数队，跟上一题一样 } printf("%lld\n",res); return 0; }
