L for LCM -Editorial || FINALE03

editorial
,
1

PROBLEM LINK: L for LCM | CodeChef

Problem Code: L for LCM | CodeChef

Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

Contest : Carnival Finale Coding Competition | CodeChef

Author: Codechef Adgitm Chapter :
tannatsri | CodeChef User Profile for Tanishq Srivastava | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Medium

PROBLEM:

Omkar is at a party, he wants to eat cakes but the cake is being served in a peculiar manner. The cakes are lined up in a row, each is numbered from 1 to N.

There are some rules at the party:

  • Each member can take 2 cakes only.
  • Each member is given a number K, he can select only those cakes whose LCM is K and their multiplication is also K. In other words let selected cake number is a and b ,1 < a, b < N then LCM(a, b) = k and a * b = k. You are given Q queries, in each query you are given K you have to find out what is the possible number of cakes he can choose.

For example-:
There are 12 cakes numbered from 1 to 12.
Let k = 12
He can choose a cake numbered at (1,12), and (3,4).
{LCM(1, 12) = 12, 1 * 12 = 12, LCM(3, 4) = 12 and 3 * 4 = 12} so the total number of ways of choosing a cake is 2.

EXPLANATION:

Use gcd concept.

SOLUTION:

C++:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
#define endl “\n”
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

vector<vector> divisor;

void find_all_divisor(int n) {
divisor.resize(n + 2);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j += i) {
divisor[j].push_back(i);
}
}
}

int main()
{
FIO;
int t, n;
cin >> t >> n;
find_all_divisor(n);
while (t–) {
int k;
cin >> k;
//1 and k is always a pair
int ans = 1;
int len = divisor[k].size();
if (len == 1) {
cout << ans << endl; continue;
}
for (int i = 0; i < (len) / 2; i++) {
if (__gcd(divisor[k][i], divisor[k][len - 2 - i]) == 1)
ans++;
}
cout << ans << endl;
}
return 0;
}