Advertisement
sabertooth09

Untitled

Dec 15th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define all(v) v.begin(),v.end()
  5.  
  6. ll const N=3*1e5;
  7. ll mod=1e9+7;
  8. vector<bool>isprime(N+9);
  9. vector<ll>prime;
  10. vector<ll>di[N];
  11. vector<ll>check[N];
  12.  
  13. void seive()
  14. {
  15.     ll i,j;
  16.     for(i=3; i*i<=N; i+=2)
  17.     {
  18.         if(isprime[i]==0)
  19.         {
  20.             for(j=i*i; j<=N; j+=i)
  21.                 isprime[j]=1;
  22.         }
  23.     }
  24.     prime.push_back(2);
  25.     for(i=3; i<=N; i+=2)
  26.         if(isprime[i]==0)
  27.             prime.push_back(i);
  28. }
  29.  
  30. void DIVISORS()
  31. {
  32.     ll i,j,p,q;
  33.     di[1].push_back(1);
  34.     for(i=2; i<=N; i++)
  35.     {
  36.         di[i].push_back(1);
  37.         p=i;
  38.         for(j=0; j<prime.size() && prime[j]*prime[j]<=p; j++)
  39.         {
  40.             if(p%prime[j]==0)
  41.             {
  42.                 q=1;
  43.                 while(p%prime[j]==0)
  44.                 {
  45.                     q*=prime[j];
  46.                     p/=prime[j];
  47.                     di[i].push_back(q);
  48.                 }
  49.             }
  50.         }
  51.         if(p!=1)
  52.             di[i].push_back(p);
  53.         sort(all(di[i]));
  54.     }
  55. }
  56.  
  57. ll solve(ll x,ll y)
  58. {
  59.     vector<ll>t1(all(di[x]));
  60.     vector<ll>t2(all(di[y]));
  61.     ll i,j,p,cnt=0;
  62.     for(i=0; i<t1.size(); i++)
  63.     {
  64.         p=t1[i];
  65.         for(j=0; j<t2.size(); j++)
  66.         {
  67.             if(t2[j]>p  && binary_search(all(check[p]),t2[j])==0)
  68.             {
  69.                 cnt++;
  70.                 check[p].push_back(t2[j]);
  71.             }
  72.         }
  73.     }
  74.     return cnt;
  75. }
  76.  
  77. int main()
  78. {
  79.     seive();
  80.     DIVISORS();
  81.     /*for(ll i=1;i<=N;i++)
  82.     {
  83.         printf("%lld:\n",i);
  84.         for(ll j=0;j<di[i].size();j++)
  85.         {
  86.             printf("%lld ",di[i][j]);
  87.         }
  88.     }*/
  89.     ll i,n,a,b,cnt=0;
  90.     scanf("%lld",&n);
  91.     a=n/2;
  92.     if(n%2)
  93.         a--;
  94.     for(i=1; i<=a; i++)
  95.     {
  96.         b=n-i;
  97.         cnt+=solve(i,b);
  98.     }
  99.     printf("%lld\n",cnt);
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement