A - （例題）整數分解

Crawling in process... Crawling failed Time Limit:2000MS???? Memory Limit:32768KB???? 64bit IO Format:%lld & %llu

Submit Status

Description

Find the result of the following code:

long?long?pairsFormLCM(?int?n?)?{
? ??long?long?res?=?0;
? ??for(?int?i?=?1;?i?<=?n;?i++?)
? ? ? ??for(?int?j?=?i;?j?<=?n;?j++?)
? ? ? ? ? ?if( lcm(i,?j) == n ) res++;?// lcm means least common multiple
? ??return?res;
}

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10¹⁴).

Output

For each case, print the case number and the value returned by the function 'pairsFormLCM(n)'.

Sample Input

15

2

3

4

6

8

10

12

15

18

20

21

24

25

27

29

Sample Output

Case 1: 2

Case 2: 2

Case 3: 3

Case 4: 5

Case 5: 4

Case 6: 5

Case 7: 8

Case 8: 5

Case 9: 8

Case 10: 8

Case 11: 5

Case 12: 11

Case 13: 3

Case 14: 4

Case 15: 2

題目大意：

給你這個程序，讓你確定這個程序的輸出，很容易可以看出，這個程序是讓你求對于一個正整數n,讓你尋找有多少i，j滿足

lcm(i,j)=n&&1<=i<=j<=n

思路分析：首先n的范圍十分大（1e14)，暴力做肯定會超時，對于LCM，GCD，我們常考慮正整數唯一分解定理，

定理內容：對于任意一個大于1的數都可以唯一分解為若干個素數的乘積，即n=a1^b1*a2^b2*......an^bn;

我們先研究其中一個素因子a1，首先i和j唯一分解后肯定有a1^k（0~b1)，同時又因為LCM（i,j)=n,則肯定有一個

數k=b1，可能的種數有（2*（b1+1)-1)（因為k1=b1&&k2=b1的情況多算了一次），由分步乘法技術原理可得

總共的可能性有t=2*b1+1)(2*b2+1)(2*b3+1)........,但是注意題目要求i<=j,i==j的情況只有可能有一種，那就是

i==j==n，由對稱性，i<j的情況有（t-1)/2種，所以最后的答案就是（t+1)/2;

tip：正整數唯一分解需要進行兩步 1.素數篩（到sqrt(n)即可） 2.枚舉素數，進行唯一分解

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include<algorithm> #include <cmath> using namespace std; typedef long long ll; const int maxn=1e7+100;// bool vis[maxn]; ll prime[maxn/10]; int tot; /*void getprime()//因為n的范圍是1e14，打表只需要打到sqrt(n)即可，最多只可能有一個素因子大于sqrt(n)，最后特判一下即可； {memset(vis,true,sizeof(vis));tot=0;for(ll i=2;i<maxn;i++){if(vis[i]){prime[tot++]=i;for(ll j=i*i;j<maxn;j+=i){vis[j]=false;}}} }*/ void Eulerprime() {memset(vis,true,sizeof(vis));int tot=0;for(int i=2;i<maxn;i++){if(vis[i]) prime[tot++]=i;for(int j=0;j<tot&&prime[j]*i<maxn;j++){vis[i*prime[j]]=false;if(i%prime[j]==0) break;}} } int a[1000],b[1000]; int cnt=0; void sbreak(ll n)//正整數唯一分解 {memset(a,0,sizeof(a));memset(b,0,sizeof(b));cnt=0;for(int i=0;prime[i]*prime[i]<=n;i++){if(n%prime[i]==0){a[cnt]=prime[i];while(n%prime[i]==0){b[cnt]++;n/=prime[i];}cnt++;}}if(n!=1){a[cnt]=n;b[cnt]=1;cnt++;//為了使兩種情況分解后素因子下標都是0~cnt-1; } } int kase; int main() {int T;ll n;Eulerprime();scanf("%d",&T);kase=0;while(T--){scanf("%lld",&n);sbreak(n);ll ans=1;for(ll i=0;i<cnt;i++){ans*=(2*b[i]+1);}ans=(ans+1)/2;printf("Case %d: %lld\n",++kase,ans);} } View Code

?

轉載于:https://www.cnblogs.com/xuejianye/p/5674803.html

總結

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

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