LightOJ 1236 Pairs Forming LCM(独一分解定理)
LightOJ 1236 Pairs Forming LCM(唯一分解定理)
大致题意:求the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j ).
数据范围:
T (≤ 200)denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 1014).
思路:把n分解成素因数的形式n=p1^c1+p2^c2+...pm^cm
假设已找到一对(a,b)的lcm=n
有a=p1^d1+p2^d2+...pm^dm
b=p1^e1+p2^e2+...pm^em
易知max(di,ei)=ci
先考虑有序数对(a,b),由唯一分解定理知,a的每一个素因数的幂的大小都决定一个独一无二的数。
所以(a,b)的种数就是(di,ei)的种数,即2*(ci+1)-1(因为有序对(c1,c1)重复了一次所以-1)
所以有序对(a,b)的种数ans=(2*c1+1)*(2*c2+1)*(2*c3+1)*...*(2*cm+1)
但是要求求无序对的种数,已知(a,b)(b,a)重复,除了(n,n)只算了一个之外,所以ans = ans/2 +1
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int N = 1e7+100; ll prime[N/10]; bool vis[N]; int tot; void ini() { for(ll i=2;i<N;i++) if(!vis[i]) { prime[tot++]=i; for(ll j=i*i;j<N;j+=i) vis[j]=1; } } int main() { ini(); int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { ll n; cin>>n; ll t=n; ll ans=1; for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++) { ll cnt=0; while(t%prime[i]==0) cnt++,t/=prime[i]; ans*=(2*cnt+1); } if(t>1) ans*=3; ans = ans/2 +1; cout<<"Case "<<cas<<": "<<ans<<endl; } return 0; }