题目大意：求两个数同余的模的个数。 思路分析： 同余定义： 设m是正整数，若a和b是正整数，且m|(a-b)，则称a和b模m同余。 那么，由同余的定义可知，如果a和b的差能被m整除，则m就是a b 同余的模，进而也就是a b的因子。 先进行素数筛选，在进行差对素数试除，得到差的因子，也可以直接对所有可能的因数进行试除。 代码分别如下： 筛素数： #include #include #include using namespace std; const int maxn=100000; int prime[maxn/3]; int flag[maxn]; int cnt; void Prime(){ cnt=0; memset(flag,0,sizeof(flag)); for(int i=2;i1;i++){ int cnt1=0; while(n%prime[i]==0){ n/=prime[i]; cnt1++; } ans1*=(cnt1+1); } if(n>1) ans1*=2; printf("%d ",ans1); } int main(){ int a,b; Prime(); while(scanf("%d%d",&a,&b)==2){ if(a==0&&b==0) break; int cnt=0; if(a>b) swap(a,b); int n=b-a; f(n); } return 0; }
直接试除： #include #include #include #include using namespace std; int f(int n){ int ans=1; for(int i=2;i<=(int)sqrt(n+0.5)&&n>1;i++){ int cnt=0; while(n%i==0){ n/=i; cnt++; } ans*=(cnt+1); } if(n>1) ans*=2; printf("%d ",ans); } int main(){ int a,b; while(scanf("%d%d",&a,&b)==2){ if(a==0&&b==0) break; int cnt=0; if(a>b) swap(a,b); int n=b-a; f(n); } return 0; }