lightoj 1236 正整数唯一分解定理

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

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
",++kase,ans);
    }
}

View Code