UESTC 1552 最大公约数（数论）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：给出N,M，找出1-N中有多少个数X满足gcd（X,N）>=M

http://acm.uestc.edu.cn/problem.php?pid=1552

枚举所有可能的M，然后求出phi(N/M)

即最后的解为sigma(phi(N/P)) (P|N&& P>=M)

直接暴力搞搞

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define maxn 200005#define eps 1e-8#define inf 1<<30#define LL long long#define zero(a) fabs(a)<eps#define MOD 1000000007#define N 47000using namespace std;bool flag[N]={0};int prime[N],cnt=0;int fac[N][2],tot;void Prime(){for(int i=2;i<N;i++){if(flag[i]) continue;prime[cnt++]=i;for(int j=2;j*i<N;j++)flag[i*j]=true;}}void Split(int n){tot=0;for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++){if(n%prime[i]==0){fac[tot][0]=prime[i];fac[tot][1]=0;while(n%prime[i]==0){fac[tot][1]++;n/=prime[i];}tot++;}}if(n>1) {fac[tot][0]=n;fac[tot++][1]=1;}}int Get_Eular(int n){int ret=1;for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++){if(n%prime[i]==0){ret*=prime[i]-1;n/=prime[i];while(n%prime[i]==0){ret*=prime[i];n/=prime[i];}}}if(n>1) ret*=n-1;return ret;}int ans;int t,n,m;void dfs(int idx,int num){if(idx>=tot){if(num<m) return;ans+=Get_Eular(n/num);return;}int tmp=1;for(int i=0;i<=fac[idx][1];i++,tmp*=fac[idx][0])dfs(idx+1,num*tmp);}int main(){Prime();scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);Split(n);ans=0;dfs(0,1);printf("%d\n",ans);}return 0;}