PROBLEM LINK:https://www.codechef.com/NITJ2021/problems/CIN004
Author: Rajat
Tester: Rajat
Editorialist: Rajat
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
HAPPY NEW YEAR
Chef wants to gift pairs to his friends this new year. But his friends like good pairs
only.
A pair (a , b) is called a good pair if 1<=a<b<=N such that GCD(a*b , P) = 1.
Since Chef is busy in preparation for the party, he wants your help to find all the
good pairs.
—————————————————————————————————————
INPUT
• The first line of the input contains a single integer T.
• The first and only line of each test case contain two integer N,P.
————————————————————————————————————————
OUTPUT
For each test case, print a single line containing one integer — the total number of good
pairs
————————————————————————————————————————
CONSTRAINTS
• 1 ≤ T≤ 50
• 2 ≤ N,P ≤105
—————————————————————————————————————
Example Input
2
2 3
3 3
————————————————————————————————————————
Example Output
1
1
QUICK EXPLANATION:
Here we need to find all the numbers whose gcd with p is 1 and then we can form pairs out of them.
EXPLANATION:
Use a loop to find the number of numbers whose gcd witn p is 1.
The number of pairs which can can formed using these x numbers is x*(x-1
)/2 i.e Xc2.
SOLUTIONS:
#include <bits/stdc++.h>
#define ll long long int
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//*******************************************************************
void input()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
}
ll gcd(ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
//********************************************************************
void solve()
{
ll n, p;
cin >> n >> p;
unordered_set s;
F(i, 1, n + 1)
{
if (gcd(i, p) == 1)
{
s.insert(i);
}
}
if (s.size() == 0)
{
cout << “0”;
return;
}
ll ans = (s.size() * (s.size() - 1)) / 2;
cout << ans;
}
//*******************************************************************
int main()
{
fast()
input();
cin >> t;
while (t–)
{
solve();
cout << endl;
}
}