Pairs Forming LCM LightOJ - 1236————（算术基本定理+容斥）

一时失言乱红尘 2022-05-18 02:58 185阅读 0赞

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)  p a i r s ( i , j )  for which lcm(i,j)=n  l c m ( i , j ) = n  and (i≤j).  ( i ≤ j ) .

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

Each case starts with a line containing an integern(1≤n≤1014).  n ( 1 ≤ n ≤ 1014 ) .

**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)  ( i , j ) 使得lcm(i,j)=n  l c m ( i , j ) = n ，其中1≤i≤j≤n  1 ≤ i ≤ j ≤ n   
问有多少对这样的(i,j)  ( i , j )

思路：对于n我们可以写成

n=pa11pa22⋯pann  n = p 1 a 1 p 2 a 2 ⋯ p n a n

同理，i和j也可以写成这个形式

i=pb11pb22⋯pbnn  i = p 1 b 1 p 2 b 2 ⋯ p n b n

j=pc11pc22…pcnn  j = p 1 c 1 p 2 c 2 … p n c n

因为  lcm(i,j)=n  l c m ( i , j ) = n   
所以

a1=max(b1,c1)a2=max(b2,c2)⋯an=max(bn,cn)  a 1 = m a x ( b 1 , c 1 ) a 2 = m a x ( b 2 , c 2 ) ⋯ a n = m a x ( b n , c n )

其中

biorci=ai  b i o r c i = a i

当bi=ai  b i = a i 的时候，0≤ci≤ai  0 ≤ c i ≤ a i 有ai\+1  a i + 1 种情况  
当ci=ai  c i = a i 的时候，0≤bi≤ai  0 ≤ b i ≤ a i 有ai\+1  a i + 1 种情况  
一共有2(ai\+1)  2 ( a i + 1 ) 种情况  
但是bi=ci=ai  b i = c i = a i 的情况出现了两次，所以我们要去重，去重后结果是2ai\+1  2 a i + 1 种情况  
又因为i≤j  i ≤ j   
所以最终的结果

2∗ans=∏i=1n(2ai\+1)  2 ∗ a n s = ∏ i = 1 n ( 2 a i + 1 )

故

ans=∏ni=1(2ai\+1)2  a n s = ∏ i = 1 n ( 2 a i + 1 ) 2

第一次做的时候没有打素数表，导致TLE一次…

--------------------

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<string>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int MAXN=1e7+9;
    bool vis[MAXN];
    int prime[1000000];
    void getprime()
    {
        prime[0]=0;
        for(int i=2;i<MAXN;i++)
        {
            if(!vis[i]) prime[++prime[0]]=i;
            for(int j=2;j*i<MAXN;j++)
                vis[i*j]=1;
        }
    }
    
    int main()
    {
        int t;
        int kase=0;
        getprime();
        scanf("%d",&t);
        while(t--)
        {
            ll n;
            ll ans=1;
            scanf("%lld",&n);
            for(ll i=1;(long long)prime[i]*prime[i]<=n&&i<prime[0];i++)
            {
                int cnt=0;
                if(n%prime[i]==0)
                {
                    while(n%prime[i]==0)
                    {
                        cnt++;
                        n/=prime[i];
                    }
                    ans*=2*cnt+1;
                }
            }
            if(n!=1)    ans*=2*1+1;
            printf("Case %d: %lld\n",++kase,(ans+1)/2);
        }
        return   0;
    }