首页 > 代码库 > LightOJ 1341 Aladdin and the Flying Carpet（唯一分解定理）
LightOJ 1341 Aladdin and the Flying Carpet（唯一分解定理）
http://lightoj.com/volume_showproblem.php?problem=1341
题意：
给你矩形的面积（矩形的边长都是正整数），让你求最小的边大于等于b的矩形的个数。
思路：
根据唯一分解定理，把X写成若干素数相乘的形式，则X的正因数的个数为：（1+a1）（1+a2）（1+a3）...（1+an）。（ai为指数）
因为这道题目是求矩形，所以知道一个正因数后，另一个正因数也就确定了，所以每组正因数重复计算了两遍，需要除以2。
最后减去小于b的因数。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int maxn=1e6+1000;13 14 int n;15 int cnt=0;16 int primes[maxn];17 int vis[maxn];18 19 void get_primes()20 {21 int m=sqrt(maxn+0.5);22 for(int i=2;i<=m;i++)23 {24 if(!vis[i])25 {26 for(int j=i*i;j<=maxn;j+=i)27 vis[j]=1;28 }29 }30 for(int i=2;i<=maxn;i++)31 if(!vis[i]) primes[cnt++]=i;32 }33 34 int main()35 {36 //freopen("D:\\input.txt","r",stdin);37 int T;38 int kase=0;39 get_primes();40 scanf("%d",&T);41 while(T--)42 {43 long long a,b;44 scanf("%lld%lld",&a,&b);45 long long x=a;46 if(a<=b*b) {printf("Case %d: 0\n",++kase);continue;}47 long long ans=1;48 for(int i=0;i<cnt&&primes[i]*primes[i]<=a;i++)49 {50 if(a%primes[i]==0)51 {52 long long num=0;53 while(a%primes[i]==0)54 {55 num++;56 a/=primes[i];57 }58 ans*=(1+num);59 }60 }61 if(a>1) ans*=2;62 ans/=2;63 for(long long i=1;i<b;i++)64 if(x%i==0) ans--;65 printf("Case %d: %lld\n",++kase,ans);66 }67 return 0;68 }
LightOJ 1341 Aladdin and the Flying Carpet（唯一分解定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。