WCPL-Editorial

PROBLEM LINK:

Practice
Contest: Hey Newbees, Here is Some Honey

Author: arghya_n

Tester: aref111n

Editorialist: arghya_n

DIFFICULTY: Medium

PREREQUISITES:

Combinatorics,Number Theory

PROBLEM:

You are given n,k.You have to find how many numbers less than n have GCD k with n.Foramlly GCD(n,those numbers less than n)=k.

QUICK EXPLANATION:

Precalculate the Phi by using Euler’s Totient Function. Then just find if n%k=0 or not…If n%k!=0 then answer is 0 because there is no such numbers which can fulfill the above condition.If n%k=0 then It can be proven that Phi(n/k) will give you the result…

EXPLANATION:

If there are some number less than n which GCD with n is k …They must be divisible by k.
So,if I divide n,the numbers less than n by k they are n/k and something which is considered for this case.Now,I can say GCD(n/k,the numbers after dividing )=1 that means n/k and number after dividing will be co-prime. Now we can compute how many co-primes less than n/k by Euler’s Totient function Phi.

TIME COMPLEXITY: O(nlog(log(n)))

Setter's Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ulli;
typedef double db;

#define PI acos(-1.00)
vector phi(1e6+1);

void Phi(){
phi[0]=0;
phi[1]=1;
for(int i=2;i<=1e6;i++)
phi[i]=i;
for (int i =2;i<=1e6;i++) {
if (phi[i]==i) {
for (int j=i;j<=1e6;j+=i)
phi[j]-=phi[j]/i;
}
}
}

void solve()
{
int n,k;
cin>>n>>k;
if(n%k){
cout<<0<<endl;
return ;
}
//cout<<phi[n/3]<<endl;
int tm=phi[n/k];
cout<<tm1LL(tm-1)/2<<endl;

}

int main()
{
//freopen(“in.txt”,“r”,stdin);
//freopen(“out.txt”,“w”,stdout);
int t,i=1;
cin>>t;
Phi();

while(t--){
    solve();
    //cout<<i++<<endl;
}

}