首页 > 代码库 > UVA 10892 LCM Cardinality
UVA 10892 LCM Cardinality
题目链接:UVA-10892
题意为给定一个数n,问有多少组不同的数对<a,b>的lcm等于n。看了AC,∑ndless的题解,直接摘抄了。
代码:
1 #include"cstdio" 2 #include"iostream" 3 #include"cstring" 4 #include"algorithm" 5 #include"cstdlib" 6 #include"vector" 7 #include"set" 8 using namespace std; 9 typedef long long LL; 10 const LL MAXN=1e5; 11 12 LL prime[MAXN+1]; 13 void getPrime() 14 { 15 memset(prime,0,sizeof(prime)); 16 for(LL i=2;i<=MAXN;i++) 17 { 18 if(!prime[i])prime[++prime[0]]=i; 19 for(LL j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++) 20 { 21 prime[prime[j]*i]=1; 22 if(i%prime[j]==0) break; 23 } 24 } 25 } 26 27 int main() 28 { 29 #ifdef LOCAL 30 freopen("in.txt","r",stdin); 31 //freopen("out.txt","w",stdout); 32 #endif 33 getPrime(); 34 LL n; 35 LL nn; 36 while(scanf("%lld",&n)!=EOF && n) 37 { 38 LL ans=1; 39 nn=n; 40 for(LL i=1;i<=prime[0];i++) 41 { 42 LL r=0; 43 while(n%prime[i]==0) 44 { 45 r++; 46 n/=prime[i]; 47 } 48 ans*=(2*r+1); 49 if(n==1) break; 50 } 51 if(n>1) ans*=3; 52 ans = (ans+1)/2; 53 printf("%lld %lld\n",nn,ans); 54 } 55 return 0; 56 }
UVA 10892 LCM Cardinality
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。