# 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

*Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9*

**Tester:***Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9*

**Editorialist:**# 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;

}