# Contest : Carnival Finale Coding Competition | CodeChef

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

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.

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;
}
{"ft_lang_label":"__label__en","ft_lang_prob":0.7720223,"math_prob":0.9897376,"size":2084,"snap":"2022-05-2022-21","text_gpt3_token_len":653,"char_repetition_ratio":0.10576923,"word_repetition_ratio":0.015345269,"special_character_ratio":0.3378119,"punctuation_ratio":0.18681319,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99843526,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-28T23:55:27Z\",\"WARC-Record-ID\":\"<urn:uuid:e4cc8d30-8180-4c84-b234-eed7287ae7a6>\",\"Content-Length\":\"15223\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bb952cfb-6f02-426c-8dac-bfc24fe93488>\",\"WARC-Concurrent-To\":\"<urn:uuid:76b514da-fc8e-41a5-90b5-21bc10b5e95d>\",\"WARC-IP-Address\":\"3.231.242.28\",\"WARC-Target-URI\":\"https://discuss.codechef.com/t/l-for-lcm-editorial-finale03/99512\",\"WARC-Payload-Digest\":\"sha1:OEY6EIA55GYRS474HTT2VDWOOMICT5YM\",\"WARC-Block-Digest\":\"sha1:OSOFSP4Y2HBWKWMCLFNYYBRIM3W6IGC2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652663021405.92_warc_CC-MAIN-20220528220030-20220529010030-00001.warc.gz\"}"}