# 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<<tm*1LL*(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;
}
```

}