Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define all(v) v.begin(),v.end()
- ll const N=3*1e5;
- ll mod=1e9+7;
- vector<bool>isprime(N+9);
- vector<ll>prime;
- vector<ll>di[N];
- vector<ll>check[N];
- void seive()
- {
- ll i,j;
- for(i=3; i*i<=N; i+=2)
- {
- if(isprime[i]==0)
- {
- for(j=i*i; j<=N; j+=i)
- isprime[j]=1;
- }
- }
- prime.push_back(2);
- for(i=3; i<=N; i+=2)
- if(isprime[i]==0)
- prime.push_back(i);
- }
- void DIVISORS()
- {
- ll i,j,p,q;
- di[1].push_back(1);
- for(i=2; i<=N; i++)
- {
- di[i].push_back(1);
- p=i;
- for(j=0; j<prime.size() && prime[j]*prime[j]<=p; j++)
- {
- if(p%prime[j]==0)
- {
- q=1;
- while(p%prime[j]==0)
- {
- q*=prime[j];
- p/=prime[j];
- di[i].push_back(q);
- }
- }
- }
- if(p!=1)
- di[i].push_back(p);
- sort(all(di[i]));
- }
- }
- ll solve(ll x,ll y)
- {
- vector<ll>t1(all(di[x]));
- vector<ll>t2(all(di[y]));
- ll i,j,p,cnt=0;
- for(i=0; i<t1.size(); i++)
- {
- p=t1[i];
- for(j=0; j<t2.size(); j++)
- {
- if(t2[j]>p && binary_search(all(check[p]),t2[j])==0)
- {
- cnt++;
- check[p].push_back(t2[j]);
- }
- }
- }
- return cnt;
- }
- int main()
- {
- seive();
- DIVISORS();
- /*for(ll i=1;i<=N;i++)
- {
- printf("%lld:\n",i);
- for(ll j=0;j<di[i].size();j++)
- {
- printf("%lld ",di[i][j]);
- }
- }*/
- ll i,n,a,b,cnt=0;
- scanf("%lld",&n);
- a=n/2;
- if(n%2)
- a--;
- for(i=1; i<=a; i++)
- {
- b=n-i;
- cnt+=solve(i,b);
- }
- printf("%lld\n",cnt);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement