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;
}
}