題意：求有多少對數對(i,j)滿足lcm(i,j) = n，1<=i<=j, 1<=n<=1e14。

分析：根據整數的唯一分解定理，n可以分解為(p1^e1)*(p2^e2)*(p3^e3)*...*(pn^en)。其中pi是每個不同的素因子。

同樣可將 i 和 j 分解為(a1^c1)*(a2^c2)^(a3^c3)...(an^cn) 和 (b1^d1)*(b2^d2)*(b3^d3)*...(bn^dn)。

因為lcm(i,j) = n。所以對任意 i，都有max(ci,di)= ei ，0 <= min(ci,di) <= ei，所以對n的每個素因子，都有2*(ei+1)-1種情況（減1是因為ci=di=ei的情況被算了2次）。

所有的可能 t 就是 (2ei+1)之積。這是有序對的數量，求無序對的時候 將 (t+1)/2，加1是因為(n,n)的情況本身只有一種可能。

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn =1e7+5; const int INF =0x3f3f3f3f;bool notprime[maxn<<1]; vector<int> prime;//prime[0] 表示當前范圍內有多少素數,prime[i] 表示第i個素數是多少 void pre() {memset(notprime,0,sizeof(notprime));notprime[0] = notprime[1] = true;for(int i=2;i<maxn;++i){if(!notprime[i]) prime.push_back(i);for(int j=0 ; j<prime.size() && prime[j] <= maxn / i ;++j){notprime[prime[j]*i] = true;if(i%prime[j]==0) break;}} }LL getFactor(LL n) {LL tmp = n , res=1;for(int i=0;i<prime.size() && prime[i]*prime[i]<=tmp;++i){int cnt =0;while(tmp%prime[i]==0){cnt++;tmp/=prime[i];}res *=(2*cnt +1 );}if(tmp>1) res*= 3; res++;res>>=1;return res; }int main() {#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifpre();int T,N,u,v,tmp,cas=1;scanf("%d",&T);while(T--){LL n; scanf("%lld",&n);LL res= getFactor(n);printf("Case %d: %lld\n",cas++,res);}return 0; }

?

轉載于:https://www.cnblogs.com/xiuwenli/p/9448342.html

總結

以上是生活随笔為你收集整理的LightOJ - 1236 (唯一分解定理)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。