lightoj 1236 pairs of lcm

清疚 2022-08-10 09:48 49阅读 0赞

1236 - Pairs Forming LCM

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1236" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1236&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1236" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1236" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">2 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

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 numberof 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 ≤ 1014)**.

# Output #

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

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>15</p> <p>2</p> <p>3</p> <p>4</p> <p>6</p> <p>8</p> <p>10</p> <p>12</p> <p>15</p> <p>18</p> <p>20</p> <p>21</p> <p>24</p> <p>25</p> <p>27</p> <p>29</p> </td> 
   <td> <p>Case 1: 2</p> <p>Case 2: 2</p> <p>Case 3: 3</p> <p>Case 4: 5</p> <p>Case 5: 4</p> <p>Case 6: 5</p> <p>Case 7: 8</p> <p>Case 8: 5</p> <p>Case 9: 8</p> <p>Case 10: 8</p> <p>Case 11: 5</p> <p>Case 12: 11</p> <p>Case 13: 3</p> <p>Case 14: 4</p> <p>Case 15: 2</p> </td> 
  </tr> 
 </tbody> 
</table>

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

Problem Setter: Jane Alam Jan

题意：求1-n中不同的两个数的最小公倍数等于n的个数。

分析：遇到这种题，暴力是不可能的，只有考虑别的方法。考虑将n进行质因数分解。从质因数中找一些线索。

因数分解以后，n=p1^a1 \* p2^a2 \* p3^a3 \* ......  如果两个数（a,b）的lcm为n，把n拆成p1^a1, p2^a2, p3^a3...若干部分，如果a与b质因数分解后与之对应的每一部分幂的最大值小于n的对应部分的幂，那么lcm肯定不是n，所以n的每一部分的幂等于a与b对应部分的幂的最大值。例如第一部分，如果a取了最大值a1，那么b可以取0-a1共a1+1个，如果b取了最大值a1，那么a可以取0-a1共a1+1个，因此就是每次质因数分解质因数的个数 cnt\*2-1 个，因为有两次（a1,a1）组合，所有情况相乘，最后除以二（每个数重复了两次）就是答案。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline ll in()
    {
        ll res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=10000010;
    bitset<N> vis;
    int prime[680000];
    //一千万以内的素数开68万
    //一百万以内的素数开8万
    //十万以内的素数开1万
    //基本除以10就行
    //一万以内的素数直接开一万就行- -
    int p;
    int main()
    {
        int T=in(),ii=1;
        for(int i=2;i<N;i++)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(ll j=1LL*i*i;j<N;j+=i) vis[j]=1; //i*i别溢出了，不要只定义j为ll
            }
        }
        while(T--)
        {
            ll n=in();
            ll ans=1;
            for(int i=0;i<p && 1LL*prime[i]*prime[i]<=n;i++)
            {
                int cnt=0;
                while(n%prime[i] == 0)
                {
                    n/=prime[i];
                    cnt++;
                }
                ans *= ((cnt+1)<<1)-1;
            }
            if(n>1) ans *= 3;
            printf("Case %d: %lld\n",ii++,(ans+1)>>1);
        }
        return 0;
    }