Saleh127

Light OJ 1236 / Number theory - LCM

Oct 27th, 2021
563
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-27-19.06.17
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. #define maX 10000008
  13. bool marked[maX+2];
  14. vector<ll>p;
  15. void sieve()
  16. {
  17.     marked[0]=1;
  18.     marked[1]=1;
  19.     for(ll i=4; i<=maX; i+=2)
  20.     {
  21.         marked[i]=1;
  22.     }
  23.     p.push_back(2);
  24.     for(ll i=3; i<=maX; i+=2)
  25.     {
  26.         if(marked[i]==0)
  27.         {
  28.             p.push_back(i);
  29.             for(ll j=i*i; j<=maX; j+=i+i)
  30.             {
  31.                 marked[j]=1;
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.    ios_base::sync_with_stdio(0);
  40.    cin.tie(0);cout.tie(0);
  41.  
  42.  
  43.    sieve();
  44.  
  45.    test
  46.    {
  47.         ll n,m,i,j,k,l,ans=1;
  48.  
  49.         cin>>n;
  50.  
  51.         for(i=0;i<p.size() && p[i]*p[i]<=n;i++)
  52.         {
  53.              if(n%p[i]==0)
  54.              {
  55.                   l=0;
  56.  
  57.                   while(n%p[i]==0)
  58.                   {
  59.                        l++;
  60.                        n/=p[i];
  61.                   }
  62.  
  63.                   ans*=(2*l+1);
  64.              }
  65.         }
  66.  
  67.         if(n>1) ans*=3; ///cause n remains 1 time == (2*x+1)
  68.  
  69.         ans=(ans+1)/2;
  70.  
  71.         cout<<"Case "<<cs<<": "<<ans<<nl;
  72.    }
  73.  
  74.  
  75.    get_lost_idiot;
  76. }
  77.  
RAW Paste Data