打卡信奥刷题（3106）用C++实现信奥题 P7281 [COCI 2020/2021 #4] Vepar

P7281 [COCI 2020/2021 #4] Vepar题目描述给定两组正整数{ a , a 1 , ⋯ , b } \{a,a1,\cdots,b\}{a,a1,⋯,b}和{ c , c 1 , ⋯ , d } \{c,c1,\cdots,d\}{c,c1,⋯,d}。判断c ⋅ ( c 1 ) ⋯ d c \cdot (c1)\cdots dc⋅(c1)⋯d能否被a ⋅ ( a 1 ) ⋯ b a \cdot (a1)\cdots ba⋅(a1)⋯b整除。输入格式第一行输入一个整数t tt表示数据组数。接下来的t tt行输入四个整数a i , b i , c i , d i a_i,b_i,c_i,d_iai​,bi​,ci​,di​。输出格式输出共t tt行。对于第i ii行如果c i ⋅ ( c i 1 ) ⋯ d i c_i \cdot (c_i1)\cdots d_ici​⋅(ci​1)⋯di​能够被a i ⋅ ( a i 1 ) ⋯ b i a_i \cdot (a_i1)\cdots b_iai​⋅(ai​1)⋯bi​整除就输出DA否则输出NE。输入输出样例 #1输入 #12 9 10 3 6 2 5 7 9输出 #1DA NE输入输出样例 #2输入 #26 1 2 3 4 1 4 2 3 2 3 1 4 1 3 2 4 19 22 55 57 55 57 19 22输出 #2DA NE DA DA DA DA说明/提示样例 1 解释按照题意分别相乘得到9 × 10 90 9 \times 10909×1090和3 × 4 × 5 × 6 360 3 \times 4 \times 5 \times 63603×4×5×6360。由于90 9090能被360 360360整除因此输出DA。我们得到2 × 3 × 4 × 5 120 2 \times 3 \times 4 \times 51202×3×4×5120和7 × 8 × 9 504 7 \times 8 \times 95047×8×9504。而120 120120不能被504 504504整除因此输出NE。数据规模与约定本题不采用捆绑评测通过对应测试点就可以拿到对应的分数但有若干个约束。约束编号分值数据范围及约定1 1110 1010a i , b i , c i , d i ≤ 50 a_i,b_i,c_i,d_i \le 50ai​,bi​,ci​,di​≤502 2220 2020a i , b i , c i , d i ≤ 1000 a_i,b_i,c_i,d_i \le 1000ai​,bi​,ci​,di​≤10003 3310 1010a i 1 a_i1ai​14 4430 3030无对于100 % 100\%100%的数据1 ≤ t ≤ 10 1 \le t \le 101≤t≤101 ≤ a i ≤ b i ≤ 10 7 1 \le a_i \le b_i \le 10^71≤ai​≤bi​≤1071 ≤ c i ≤ d i ≤ 10 7 1 \le c_i \le d_i \le 10^71≤ci​≤di​≤107。说明本题分值按 COCI 原题设置满分70 7070。题目译自 COCI2020-2021 CONTEST #4T2 Vepar。C实现#includebits/stdc.husingnamespacestd;constintmaxn10000005,maxe5000005;intT,a,b,c,d,k,tot,zhi[maxe];boolvis[maxn];inlineintread(){intret0,f1;charchgetchar();while(!isdigit(ch)){if(ch-)f-f;chgetchar();}while(isdigit(ch))retret*10ch-0,chgetchar();returnret*f;}//快读voidmake_p(){memset(vis,1,sizeofvis);vis[0]vis[1]0;for(inti2;isqrt(10000005);ii%21?2:1)if(vis[i])for(intji*i;j10000005/i;ji)vis[j]0;for(inti2;i10000005;ii%21?2:1)if(vis[i])zhi[k]i;}//筛法挖素数stringcheck(){intsxa-1,Sx0,Sy0,syb;intpxc-1,pyd,Px0,Py0;for(inti1;zhi[i]max(b,d)ik;i){Sx0,Sy0;sxa-1;syb;pxc-1,pyd;Px0,Py0;while(sx)sx/zhi[i],Sxsx;//快速求出次数while(sy)sy/zhi[i],Sysy;//快速求出次数while(px)px/zhi[i],Pxpx;//快速求出次数while(py)py/zhi[i],Pypy;//快速求出次数if(Sy-SxPy-Px)returnNE;//如果有质数的次数在除数里比被除数高那么就返回 NE}returnDA;}//判断核心intmain(){Tread();make_p();while(T--){aread(),bread();cread();dread();coutcheck()endl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容