Aladdin and the Flying Carpet 算数基本定理
题目大意：给出面积n，和最短边m，求能形成的矩形的个数（不能为正方形）。
~一天自己傻huhu的以为枚举……那么大数……12次方……不管咋说都是不对的~
看了题解发现是考的是算数基本定理，还真没看出来，sad……
根据算数基本定理有:
1.每个数n都能被分解为：n=p1 ^ a1* p2 ^ a2 * p3 ^ a3……pn ^ an(p为素数);
2.n的正因数的个数sum为：sum=（1+a1）* (1+a2) * (1+a3)……(1+an);
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define MAX 1000005 #define mod 1000000007 using namespace std; long long p[MAX],v[MAX],num_prime; void GetPriem()//获得素数 { memset(p,0,sizeof(p)); memset(v,0,sizeof(v)); for(int i=2;i<MAX;i++) { if(!v[i]) { p[++num_prime]=i; for(int j=i;j<MAX;j+=i) v[j]=1; } } } long long Ans(long long n) { long long cnt,sum=1; for(int i=1;i<=num_prime && p[i]<=n;i++) { if(n%p[i]==0) { cnt=0; while(n%p[i]==0) { cnt++; n/=p[i]; } sum*=(cnt+1); } } if(n > 1) sum *= 2; // 这里一开始一直不明白，后来问小姐姐，她说是因为数据太大了，而我们打表只到了10的7次方，所以如果遍历完了n还是大于1的话，应该它本身就是一个质数就是sum乘以（1+1）即可。 return sum; } int main() { GetPriem(); int T,cnt=1,i,j; long long n,m; scanf("%d",&T); while(T--) { scanf("%lld%lld",&n,&m); if(n/m < m) { printf("Case %d: %lld\n",cnt++,0); continue; } long long ans=Ans(n)/2; for(i=1;i<m;i++) { if(n%i==0) ans--; } printf("Case %d: %lld\n",cnt++,ans); } return 0; }
卑微……
