打卡信奥刷题（3049）用C++实现信奥题 P6659 [POI 2019/2020 R1] Najmniejsza wspólna wielokrotność / 最小公倍数

P6659 [POI 2019/2020 R1] Najmniejsza wspólna wielokrotność / 最小公倍数题目背景Byteasar 正在准备他的数学考试。题目描述老师跟他说考试题目中有关于最小公倍数l c m \rm lcmlcm的题目于是他找到了一道题练练手。给定一个整数M MM求一个区间[ a , b ] [a,b][a,b]使得M MM为这个区间所有数的最小公倍数。因为您很强所以 Byteasar 在解出来这道题的同时也想问问您这题的答案。因为 Byteasar 非常爱问问题所以他要问您z zz组问题。输入格式第一行一个整数z zz代表询问个数。接下来z zz行每行一个整数M MM代表一个询问。输出格式z zz行每行两个整数a , b a,ba,b代表一个询问的答案。如果有多组解输出a aa最小的。如果还有多组解输出b bb最小的。如果无解则输出NIE。输入输出样例 #1输入 #13 12 504 17输出 #11 4 6 9 NIE输入输出样例 #2输入 #25 5 6 7 8 9输出 #2NIE 1 3 NIE NIE NIE输入输出样例 #3输入 #31 1000000输出 #3NIE输入输出样例 #4输入 #41 99999990000000输出 #49999999 10000000说明/提示样例说明对于样例1 11的第一组数据12 1212为区间[ 1 , 4 ] [1,4][1,4]的最小公倍数。另一组附加样例见附加文件的 sample.in 和 sample.out。数据规模与约定本题采用捆绑测试。Subtask 118 ptsz ≤ 10 z \le 10z≤10M ≤ 1000 M \le 1000M≤1000。Subtask 220 ptsz ≤ 100 z\le 100z≤100M ≤ 10 9 M \le 10^9M≤109。Subtask 320 ptsz ≤ 100 z \le 100z≤100M ≤ 10 18 M \le 10^{18}M≤1018。Subtask 442 pts无特殊限制。对于100 % 100\%100%的数据1 ≤ z ≤ 10 4 1 \le z\le 10^41≤z≤1041 ≤ M ≤ 10 18 1 \le M \le 10^{18}1≤M≤1018。说明翻译自 POI 2019 A Najmniejsza wspólna wielokrotność。C实现#includebits/stdc.h#defineintlonglong#definegcd(x,y)__gcd(x,y);usingnamespacestd;constintINF1e18;intT;mapint,pairint,intmp;voidinit(){for(intl1;l1500000;l){intkl*(l1);for(intrl2;;r){k/gcd(k,r);if(kINF/r)break;k*r;if(!mp.count(k))mp[k]make_pair(l,r);}}}pairint,intcheck(intx){intl1,r1e9;while(lr){intmid(lr)1;if(mid*(mid1)x)rmid-1;elseif(mid*(mid1)x)lmid1;elsereturnmake_pair(mid,mid1);}returnmake_pair(0,0);}signedmain(){init();cinT;while(T--){intx;cinx;if(mp.count(x))coutmp[x].first mp[x].second;else{pairint,intdaancheck(x);if(daan.first0)coutNIE;elsecoutdaan.first daan.second;}cout\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容