Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

Solution code:
n,a=int(input()),list(map(int,input().split()))
g=0
from math import gcd
for i in a:g=gcd(i,g)
if g!=1:print("not coprime")
else:
    from collections import defaultdict
    memo=defaultdict(int)
    for i in a:
        for p in range(2,int(i**.5)+1):
            if i%p==0:
                while i%p==0:i//=p
                if memo[p]:
                    print("setwise coprime");exit()
                memo[p]+=1
        if i!=1:
            if memo[i]:print("setwise coprime");exit()
            memo[i]+=1
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91&<y|p00000KmY&$00000;4c6G0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000sv7_R00000sv7_R00000001BW000000RR911^@s6C>;O*00000C><aG00000C><aG00000@B#n;00000SOow800000001BW000000ssI21^@s6Kpg-800000Kph|e00000Kph|e000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4Bp3hy00000Bp3hy00000Bp3hy00000bN~PV00000bN~PV000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4C>;O*00000C><aG00000C><aG00000*a83m00000*a83m000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$r40#J>9(qerLBGgm`8xN_NpRK0ssI26#xJL0RR911^@s6000mI0RRL56#xJL000006qpP{bCw4J000000000000000000000000000000y#N3J5&!@I00000000000000000000-2eap5&!@I00000000000000000000)&T$jA^-pY00000000000000000000!T|sP5&!@I00000000000000000000RR9105&!@I00000000000000000000$pHWW5&!@I00000000000000000000)&Kwi5&!@I00000000000000000000VgUdE5&!@I00000000000000000000u>k-85&!@I000000000000000000006afGL5&!@I00000000000000000000XaN8K5&!@I00000000000000000000<pBTy5&!@I00000000000000000000{{R305&!@I00000000000000000000U;qFB5&!@I000000000000000000009{>OVAOHXW00000000000000000000m;nF)5&!@I00000000000000000000?EwG)5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000r2qf`5&!@I00000000000000000000fB^si5dawgKp-Fh000005CH%H00000oB#j-5dawgU?Cs?000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q)zN@MN(-1Us_I6bU9*Sb7^B=X>W5$V^ef7F=J?9a$j_EVQF-8Nn=GtHDhdLVRA)NbTKktNpEvsNpEv>VRU5xUs_XiGh=CP0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`Bn0AE^DbTKzyUvy}4Z+Bl}VPs!nY;131b^u>mWNc7&0AE^8Q*=0KZ*yN_VRL0MHFJ4xV_$b^bZB35bYy97MPdM7UuSrDUvOn|b8l{8Y-x0PUv@A6Us_XiF*aXcZ*z2VWnpb!X>N06a&$>!Q*<#gV`yP=UvzR|X>@Z*V?{+$Q*<#iVqtS>V_$D`baG{3ZAnyLR4`vfQ#M~vOH(snYye+cZg*_}Us_I6bU0~mb6;X%b7eG1ZfSHwF-3L&Us_XiG-GddbO3B=VrOGxUvn;VZ!R$aUsY~*X>Md+Qe|^>ZDjy#X<}n8b8jv-0AF8obYWv_Ut?%%UuI!xYyfj~a%^R80AF8Ycwt{*bY*yHbO2vpV|Za-W@&C=Y-xIB0BvP$ZEtpE0AF8hX<}nvb97;HbYE>@X>I^VLqlIPE-(N`Oi4mRUotK<07pzoLPK9NE;24P07F<<K|)DiF)lLzM@&gVLs(c}GcGhPIRHmYNkT(dSYI<PGynhq0ssO40{{a60ssR50ssO41ONp90ssR51^@y8000L70{{R3000620ssO40RRC2iU9xs5C8xGAOHXWP$qc`000L7{{a91000000RRF3rvU%}5C8xGFaQ7m6lrM<000C42Lb>95C8xGbsA|2000935dr`J000000RRI40RR915C8xG00000)30j<000I69RdIV5C8xGiGL{q000F5C;|Wg5C8xGbSaVu00062HUa<u00000C><aG000002mk;800000&<+3q00000FdZNO000002mk;800000pbY>300000I2|AW000002mk;800000kPZL<000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60{{R30000000000*dHJO000001^@s64*&oF0000000000;2$6W000001^@s65dZ)H0000000000=pP^e000001^@s65&!@I0000000000@E;%m000001^@s66951J0000000000_#Yqu000001^@s66aWAK00000000005Fj7`000000RR914FCWD0000000000Kp-Fh000001poj56#xJL0000000000U?Cs?000001poj5761SM0000000000XdfT|000002LJ#70RR910000000000a33H5000002LJ#70ssI20000000000cpo4D000002LJ#71ONa40000000000fFB?L000002LJ#71poj50000000000h#w#T000002LJ#71^@s60000000000kRKob000002LJ#72LJ#70000000000m>(bj000002LJ#72mk;80000000000pdTOr000002LJ#72><{90000000000s2?Bz000002LJ#73IG5A0000000000upb}*000002LJ#73jhEB0000000000xE~+@000002LJ#73;+NC0000000000z#kw0000002LJ#74gdfE0000000000$R8j8000002LJ#75C8xG0000000000NQ3MMNQ(u96(9geg}`(I|IkQ-#0bLx|25(iAOQa*<P;zP4<A4P|0UuSAOL6p0002#;Q#;s|0UWKAOL6q0002#(EtDc|0U8CAOL6r0002#!2kdM|0T*4AOL6s0002#u>b%6|0Ti{AOL6t0002#p#T5>|0TK<AOL6u0002#kpKVx|0S{%AOL6v0002#fdBvh|0SvvAOL6w0002#aR2}R|0SXnAOL6x0002#VE_OB|0S9fAOL6y0002#Q2+n`|0R+XAOL6z0002#K>z>$|0RkPAOL6!0002#F#rGm|0RMHAOL6#0002#ApigW|0Q}9AOL2N0000000000K~_OkG5<kSRZ~cV>@Z|Viv%So0000;i9{qQF~H~z|Ns9;jdUaoNR2(w6(9ge#|5qyAOHXW008I_|Ns9;V_YN*NQK)Egrflf07$t1|NsC0|NlQoIl~W!r~v=~OpPp^00000Oo{L45dZ)GNr}WUzz-h)LB|Ay00000NQ1xuNIAoG?@a;aOo`)2jV)>wAOKA{<#ZVjA4C8ENQvG^iSOv8{{R0-gTn+#Io);aztpBZ0O-R0|Nlsd!$^&j)TTWENQu}FA4C8E#{d8T002mXzywG+!gcYBL?jG_z<zH`jdUasy#W9K01qF400000L5p;({7i}W=o<$B07#2`BoIi8bR-x^IrnrdNQwGp4<Cd800000NMizn_yKeeNR14Givfkee{O@o0f_-fgTe$zIo5UHNQM7&1?VRJ|Nn{TNQ1=zIYcB3f1*f@JvR#g0O+0q002md-{=PZ|Nl*e<a7v3iRb9~{r~?lz(|XHBq(G^Gdv|I0000Fg@6D607!$xFk4+gTtQtyUc+V&A4C8ENQM7&1?a~8|Nl)n>~tbciQqB74<A4PNn<cbWBBO30RR9=gTMq$ImLDCgXjTt4oHnX-3kBz=pzCE0PBNDjXl2#008I}0ssK%a{vGTztpBZ07WtFMKR>)fc^jfNQuMgx&HtE=o9__|LA`G|Nlsd-$;qY=u`dw|4oJDbO=m|=jcZL|Nlsd@93`m|Nlsd#p~;44<Cd800000NR2(x6d(XdgX{?CVEzC9NQ*r|5+DFbjTK4~AOJ{>HMA5U07!$x2<h_t|Nmx?G3`l-(OyW2;z)z!@K97tjRpD%002mh4TA{)07#8JZ2kZL{}tvDAOQ3aA4C8ENR2%a5+DFoNR0&v5+DFbIrvD4<#ZWHiv_w7AOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2(w5g-6ajWx;<AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(u55g-6ag}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIZ<8AOHY$FGzzuFA*RB098nd<#Y^4i#=KqAOPr{{Qv*xNdN!;#s#?(AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8ENQwGL!TLW)iO@(f_(&<xNQL%z6G(;sbQVa3_H`Na!w(;T00000NcY}Ih5vO3NQv;n4<A4PNQuWW$w&$J^GFZ8$n!`Ky#Gkk_zxcdG0F2t54_Gu)BZ>~#(fD$iNZ*U@JNZ)NGZm3<B9o5)8NBqE)O4s0000001qDkQ%HmC5M)S;1SKc{002mdL?j3?z(|GvbWTW#`{*9~|NlshJ+}}b07!|#NQvI)Z2SNJNR4zP2S|-Qpb#Jcx&Z(H0LDZl2MXv>`~Uw)i$o*{WJogvB`5#@0CgxxgTxS9!w(+-NQ(t=5Fh|ZjXi1*AOJ`Mc<76FAcM{U=u7+m|Ld*j1pEL04<A4PNICuwgns}406|tvjduh=RY{5UK~zbJ{7E_XRZ~of^K~feR}UWmNjcnf5lD&JOo{hQiRMfx;^^}F|NlsX!vsNzEF?)e-E=XFD?vLfBz)D2Q~XGcL;N|_d<E+;NQuaaPy~xm{78*R{5jQp?};c#gTn+#Io);7TU|k1L0v&!!w(+-^TTEjA4C8ENQu~qDC^v24<Cd800000NR2}OK~+IiNr}}}Q%Q-$L4)N1Nx|$tNdd%3(fmv~<`0ee0000<iSlL-A4C8ENsU4QOpOEpOpOf3O^sOpL5l%OjVzywT>v@5eh5j4>514)iP%j!;6jN6mraSne9ldU?R0TTjX?iMiNZ+1>OV*U!bs8jNjdO-Ktziamqa<ye;MmF4<Cd800000M2i%MNr})%iNZuV(S9CAi4=!SjY9uSjSQDeiNHv~=s!#Wz(~>fNIBMg(?N*|TU|k1L0!XU4<Cd800000Nr~_eA4C8ENR2}NNQuHo!RkLq0m4Yp`b;^(bP`UD42S7(|NsAH4<Cd800000ON~ST0Zfeyhe3-GLWvZINr}MePyhe_4<Cd800000O@-}rt4xgyx9gG*A4C8EK~_OkNr}}+iSj{IRY)oNQ%HmQKo5?20RR9^h3!d+{7H%S4}|#u002mhZv;q*^Gqq@L5qAO1WAMK0Z7670*hAsMT-O^NQu};!RS9o0mDeq`$>%qoQnZD$9-uz&<~6@0RR9w*L-O~i994li9{p>i&p$diR(y-@edyWL^;PviQa!NIoC*yLHvDSNR2`G4<A4PNQuEngXjc{Py{*GeDX*+*>+Wl6GVvti&6YRi##Mmi$erRgTn;tzYiaP00000IoEujInWP{$p8QVL5UP3M2SZHM2W&di##Mni$o*@>y2g)A4C8ENQuEnIoWr!4<Cd800000Oo{49iQnk;{{R0-iP}sl;z)z~Kz@Bqh3!a*-VcQi|Ns9;iPK2I`vORfYyL>l{p$%2A4C8ENQ3PGNQ3MML5mEmNQv%h07!}2Oo`{{eEt9bNQLcLUUl6`gYE>7L5l<=Oo{VBiw;PG><COL<1zL~iP}tw=ShR^1VM>L1Zn_C!TJK|ME(E&NQ3(XSXzI~TU|k1L0v&!!$FAzBt(e;MT<lv1VM{DB#T!3>B9d1|7I=^AA|q^0001xL03UmNs0bJRY6o$Q%HmCD24V&#|Hoa002nGM+g7_002nGM-Tu2000k;6afGLiS;qbMKR>N0RR91LA?P0008R~4<A4PgTnzqiQPmGuj@fM?SEN`=$ZHXh0;NZ$93gRIc5+KgbM)x06~cyBuRtB1Wk!%2t+yUbjnSOZV*j5<qw1f0ssJm!vRH!JS0hj!~{W!-A##R2t*IB>p?l~ez9gQ4<Cd800000Njc09go^+G08EMFx<3E_07!|?NGZ!qiRMU&3?xX2*hs<n0!R<Nz(|AeKS-EJDZ)qr(&$$G|NlsX`#?yG3?zPRNQ3MMNR3%QNQuvC07!}6=x6)?|4cdKSzdHBi!+N;{78*M{5kS}4(Ub#003qWA4C8ENQuaaPy~xm{78*R{5jTq??{8g1c@+AIpcNANQ1;EOo{MYT|rzyT|r(!U&CfD4<Cd800000NQ3MMOo`@5iO*^P=>Piv|5#e<&kr8}Oo`w~Dac5PL?j4E!T175g}@Jl@Bjb+NR2!INICdOi993^hSC8507%CKB>eyX|455GB<Qa7|Nlsd!A*+>NQ*=y2u+FMO)0@mIpB#L0dyryiONig#z=|JOo>b+5KM_gBnare_5c4&i%cXCOp8P$2uO*+NsC4ZPK{Iv1WAd(O)23_IpB0JOo_@&iPubt=17T5Bp6JIL?jSQiA*F2=zsP9|455WBp6JKL?jSNiNZ{aOe6?Rg}_gZBnosAOo_)xiA*F2=m+)x|455WBnU{01SCm`4o!(>2uK0QNr^@f=@kC|{|_GkNQu};gTn+&Ipc{i4~3Tg|NrU5{{R1wNXG;u1ONa4=^X$6{|_GkOo`w~Dac5PL?j4E!T175g}@Jmu>b%7NXG;u1ONa4NQ*oq=%@7m|450!NQ*=y2u+FLM2S2BO^ZHFDfmq}=X4uPiNZ*U&rFH_Oo>D!2<W=>|Nl&jL?j4EiNQ&WMhH%gOaTN*iNH-M;7mE-bR|rQ!c2+JOo{GDiA*FAOo>D!2<V3N|NlsfOe7FYi$o*{Nr}Nth5t{DBms01Oo{(UiA*F2=o9q+|455WBnU{01SCm`4o!(>2uK0QNr^@f>F@mi|45BI07yCbNQpcob~;GM1SI_b|NrSd|Ns9;zW@LK|NsC0KS(+E4~HB6|Nk+`NQM6oge3m||46~$14xMkB<TzO|Nmx?NWTC7|NsC0|364MG$ePnG08}SJR|@Qg#Z5k|46~$14xMkB<be<|NlvgK1hkfNQM7&1?YD3|Nlsd-{{`+|Nmw#4<Cd8000004<A4PL03UmNr~4%RY6otjU}c9AOKZJjV-PPAOKTAiTz25_Dm_|NQ3MMNWuLB=(qC!|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3aA9e3cWHBFAY*TEa%pX40CQz@cWHBFAY*TEa%pX40B&z|AY*TEa%pX4000000UHB5Z~y=R4FCWDO!EK#yZ`_IEc5^W<NyEwJoEqmoB{v<eD(kT<N^Qyto8r@i~s-ty!QY9`~Uy|Joo?q5CH%H%=iEQGywnrZ215GgaH5mocaI%ya50JT>Jn3Gy(tsO#lD?`~m;~y#N3IL<0Z-6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|S81?`ED*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|Si1Gjb-~a#s01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)K=S|p2mk;800000000005C8xGTmS$7xb^@4a{vGU00000AOHXWZ~y=RB=-ORi~s-t06`8Ag91bjAOc<r4iG^O2t*42OaK4?lmGw#koN!omjD0&080)Kjsivw7>xr(4j_yKM-C{41wjrlg9ZX$4k$qmAVLlpLJkl@4hTfU#>~ymNDeTA28IQU1dRiZ0ssI2Gynhq<NyEw;P(IjD**ri07ecFjRHar7>ol%4j_gEK@KQ`1p>4R4j@4e7(xyZLJkN@3jhEBQ~&?~9033T*!TbcwE+MC074EBjsijs7>xr+4j_yKK@KQ}1w;-og9ZaH0S-7x4nR*1I6)3DRSq~+4nR&0I6)3DLkbQkK@K274j4iX5JC<JK??u?8~^|S000000eVnOQUC#X5C@yZ1t0($8w>{skO2SyWB>pFBme*aAo>6Q;sXEx1Q!7S074EBj{-st7>)x)4j_#LLJla51wjrlh6X_nID-d74qyW34roaZa7+$pK@MPg3Jy3#4lqFuC_)Y(LJk;04iG{P2ulk@4roXYa7GSjK@MO5L;wH)i~s-tnDGDqHv#|v1it_P074EBjsijs7>xr&4j_yKK@KQ}1wjrlg9bznU;~2z3Jx$q4k$qmAVLlpLJkl@4hTmJ6aWAKL;?T+kn;ckE&u=k080)KUJeKVL;wH)Tmk?9Nc{i*WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGqyhi{aQy%O0ssI20000000000|Nj9Dtpkh#$_D`52L%8C|Nj9N9#Q}RrU4kT1OR{n>j9Dk0Q&<s000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000&<+3q00000pbY>300000kPZL<000000RR91000000RR91000000RR9100000iU9xs000000RR9100000rvU%}000003;+NC00000SPB3D000004FCWD00000<QD({0000082|tP00000C><aG000008vp<R000005C8xG000008UO$Q00000I2|AW000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000=mY=&000001^@s600000zybgO000003IG5A00000LIMB)000003jhEB000007ytkO000006#xJL0000000000000000{{R300000P#+)w000000ssI200000H~|0v000006aWAK000002LJ#7000007XSbN00000APE2f000002LJ#700000=m!7*000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000SO)+A00000|NsAQ000000{{R300000@c;jB00000DhB`n00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Kph|e0000000000000000000000000h6(@x00000mI?p>00000rV0Q600000wh90M00000#tHxc00000)(QXs00000<_Z7+00000_6h(1000001`7ZH0000077G9X00000CJO)n00000HVXg%00000MhgG{0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9=mY=&000000000000000000000{{mADhB`n000000000000000000000{{pBSO)+A000000000000000000000{{sC=m!7*000000000000000000000{{vDAPE2f000000000000000000000{{yESPB3D000000000000000000000{{#Fa0&nb000000000000000000000{{&GPzwM6000000000000000000000{{*HU<&{M000000000000000000000{{;I<QD({000000000000000000000{{>J@D~68000000000000000000000{{^KBp3hy000000000000000000000{{{Lm>2*6000000000000000000000{{~MfExe+000000000000000000000{|2NC><aG000000000000000000000{|5OI2|AW000000000000000000000{|8PKph|e000000000000000000000{|BQP#+)w000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000004*&oF0ssyGz!3ld00000wE+MC00000jQ{`u0ssyGpbY>300000E&u=k00000tpET30RR~Qc_JVH000000RR9100000yZ`_I1OV~>00000000000000000000#{d8T0ssyG01f~E000000000000000$p8QV0ssyGKn?%^000000000000000+yDRo0ssyGkPZL<000000000000000@&Et;0RR~Qcp@MG000000RR91000000RaF20RR;MI2|AW000000000000000C;<Qf0ssyG&<+3q000000000000000Gywnr0RR*LC><aG000000000000000yZ`_I1OV~>00000000000000000000Qvm<~0RR#Jd>a4&000000000000000000001OV~>00000000000000000000VF3UD000pHBp3hy000000000000000bO8VW0RR>NKph|e000000000000000eE|Rf000yKI2|AW000000000000000jsXAw000yKC><aG000000000000000p#cB@0RR^OP#+)w000000000000000w*deE5C9ke7$6`3000000000000000a|8eYAOIKu03aX$000000000000000z5xIL5daVX@D~68000001ONa400000%>e)a5&!@I00000000000000000000^8o+=A^;8m@DBh000000mjD0&00000WdZ;I5&!@I00000000000000000000lmY+%A^-pY00000000000000000000umS)85&!@I00000000000000000000!~y^S5&#YWU<&{M00000Hv#|v00000$pQcXA^;8mU=IKQ00000i~s-t00000+yVdqA^;8mkPrX>00000D**ri00000Qv(115ds(h2p}K;000000000000000U;_XE5&!@I00000000000000000000cmn_cAp#fx5Fj7`000002mk;800000p#=Z{5&#bX<QD({000000000000000lmh?&5&!@I00000000000000000000t^)u75&!@I00000000000000000000cLV?c5&#YW&<y|p00000D*ylh00000!UF&R5&!@I00000000000000000000)dK(k5&!@I00000000000000000000xdZ?J5&#PTSPB3D000000000000000@dE$=5ds(h7$6`3000000000000000{R0315&!@I00000000000000000000S_A+95dawgKp-Fh000005CH%H00000aRdMW5C9ke03aX$000000000000000i2(or5C9nffFd9O000000000000000egpsj5C9nf7$6`3000000000000000iUa@v5&!@I00000000000000000000uLJ-95&#YWa2Ego00000WdHyG00000oB#j-5&#YW;0^!)00000a{vGU00000zXSjP5&!@I00000000000000000000)C2$k5&!@I00000000000000000000^#lL_5&!@I00000000000000000000J_P^(AOHXW00000000000000000000S_J?A5&!@I00000000000000000000as>bYA^;8mfD-@!00000;sXEx00000mjwU-5&#YW;1>V@000000ssI200000rv(525dawgU?Cs?000007y$qP00000y#)XO5&!@I00000000000000000000+ywvtAOHXW00000000000000000000>jeM+AOHXW000000000000000000001qJ{B5&!@I0000000000000000000007YLzZ*X#HZDlTFaBu)$T2pi}HeX+9Zgg^Qb8m8VUu<u0a7j)%Utec#bzft6criC$Uv6)5ZDDL*X>?_BVRUbDNl<B1bT)QnV{~tFNoiAINohqzMMZ2*Q!rmOUte!<b1^kvNpxj$Uu<P_b6;t6WpYJDc2r+eIbT#TUsN$)E@^XeVJ<W_0AEK;PeMUVUte=|VqZyLUs^FRVrgz+a(Q28V`O-E0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44Wn^J=VE|uAPhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT2pi}HeX+9ZgXXFbZKvHUvqDAbV*J*Utec#bzft6criC$Uv6)5ZDDL*X>?_BVRUbDNl<B1bT)QnV{~tFNoiAINohqzMMX|iFkdxaUvF@8F*RRFbY*g1Y-MwEUukq@az#aUR9{m$UsNz(0AE^8Q*=0KZ*yN_VRL0MHFJ4xV_$b^bZB35bYy97MPfieM@&gVLs(c}GcGg$UteQ*VP9rxZeeU`dSyUBM@&gVLtip3GA=a$b98cSWo|$~M@&gVLtip3GA=a$ZDDC{0AE@+aB^vGbZl-(P)lP)c2r*gUs_XiF*9FZVPtA`b97&5WnpkhPB~v+XKr<0V|aKmH(y_FZ*py6Y+q?~WpZJ3Z*oacX;XAIc4cF9Z*oa#Q(;MIMMXtLY-vtYFkdxaUvF@8F*RRFbY*g1Y-MwEUukq@az#aUR9{puUsFL}R54#vGG72+Uu1J{Uua=&WNc*sUs_I6X>xN#QfWXyM@&gVLs(c}GcGg$L{~0yWo9m4UuSrDUvOn|b8l{8Y-x0PUv@A6UteQ*VP9c%Wq4_HKtM-KNkT(kGA=SMH2_~)WNc7&KtM-KNkT(dSYI<PGyq>(Zg*`!Ku1hTLPJ<sUo$Q=0AF8obYWv_Ut?%%UuI!xY(PLqOi4mRUotK<0AF8JO+#NrPDEc{0AE^DbTKwxUvG1Ca%Ev{UukZ0WpZ>$V^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kP)k!YUu-}?M@&gVLs(c}GcGhPIRIZ;Q*<<AZ*_D)Ku1hTLPJ<sUo$Q=0AF8ZVRT_%b97;HbO2vpVsmp}b97;HbO2vkPE&L^X>W61VqtS-G)Zo0bVD&kc0fQ!Oi4mRSXf^(E;ImNUu<b&V_#!)bzf<2X><T>Wo>P5c4a_7M@&gVLtip3GA=a$Utec<cwca3a&vEPVQgu1d0%!gKtMxSSV2NbUokE-0AE^8Q*=3EVRLC?Uukc1Nn=xVF)?FkVRBz|a$#w7b4g=GMKxn=WnpqfQ*<#hUrBFsUrBFsbYXO5KtM-KNkT(dSYI<PGyq>oR83!GWpZU_X>)XCa#T%2Y;SI5RAFLlWdL7QZg**JWM5Kcb9HTHKtM-BLtis4FaTd#H)LscX>)IKNohq>bT)QnV{~tFNmO4`VM$XlUqwYzF<$^*Uu<b&V_#!)bzf#_ZfO8tT2pj0V`*+cKu1hTLPJ<sUo$Q=0AF8hX<}nvb97;HbYE>@X>LG3M@&gVLtip3GA=a$Utec!Z*E_6bYXIIUta)UNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`BnKtM-KNkT(dSYI<PGyniDb9rraVPXI-b98caVPXI-b7*sPa&%#004`~6bY*gI04{ECbY(6<LP;%jVP^m?Zf|sDE@y6aE@E|QY-BBIWB@K_ZgnnbVRL8zE@XLbb9rq5E@XLbb98b5E@y6aE_P*db7^mG04`^4buM;ga&u{KZeMZ$E^=jTVJ>8OZU8QFWo%(CaBOq{E@^IQbO0`JY;-PXZ*%}IbY*yS04`=}ZfO86a&Kf|bYTE4WoTb!a$#*{Uua}<04`-{UuJS)ZDjy1XJcbuWq4y{aCBdEVPb4$04`~6X>?y<a&lpL04`=}ZfRd(a&lpL04`*CZeeX{V*oB>VRT^tE@E?Y04`&1ZEa<4bN~PV00000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO00000C;|Wg000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000=mY=&00000=mY=&00000LIMB)0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000DhB`n00000DhB`n00000E&u=k000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000SO)+A00000SO)+A00000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000=m!7*00000=m!7*00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000APE2f00000APE2f00000H~|0v000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000SPB3D00000SPB3D000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000a0&nb00000a0&nb00000-~a#s0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000PzwM600000PzwM6000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000U<&{M00000U<&{M00000f(!rv0000000000000005C8xG000000000000000qW}N^0RR911^@s600000<QD({00000<QD({000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000@D~6800000@D~6800000F#rGn0000000000000001ONa4000000000000000u>b%70RR910ssI200000Bp3hy00000Bp3hy00000bN~PV0000000000000001ONa4000000000000000zW@LL0RR910ssI200000m>2*600000m>2*600000=mG!$0000000000000002mk;8000000000000000$p8QV0RR910ssI200000fExe+00000fExe+00000DgXcg0000000000000000RR91000000000000000+W-In4gdfE0{{R300000C><aG00000C>;O*000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000I2|AW00000I2`~0000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000Kph|e00000Kpg-8000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000P#+)w00000P#*vQ00000umAu60000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000SO@?B000008~^|SF8}}l2mk;8000007ytkO000002><{90{{R300000000000000000000peO(U00000Dh2=m0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000$}Ru^000005CH%H0000000000000000RR91000000000000000"

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
import math
from collections import deque

n = int(input())
als = list(map(int, input().split()))

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if i != 1 and als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        if not failed:
            ans = "pairwise coprime"

print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import reduce
from math import gcd
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    if reduce(gcd, A) != 1:
        print("not coprime")
        return

    M = max(A)
    sieve = list(range(M + 1))
    for p in range(2, M + 1):
        if sieve[p] != p:
            continue
        for i in range(2 * p, M + 1, p):
            sieve[i] = p

    used = [False] * (M + 1)
    for a in A:
        primes = set()
        while a > 1:
            p = sieve[a]
            primes.add(p)
            a //= p
        for p in primes:
            if used[p]:
                print("setwise coprime")
                return
            used[p] = True

    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def solve(N, A):
    def osa_k_construct(n_max):
        min_factor = np.arange(n_max+1)
        for i in range(2, int(n_max**0.5)+1):
            if min_factor[i] == i:
                for j in range(i*i, n_max+1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i
        return min_factor

    def osa_k_factorize(min_factor, n):
        min_factor = min_factor
        # n_twoes = (n & -n).bit_length() - 1
        # res = [2] * n_twoes
        # n >>= n_twoes
        res = [0]*0
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

    osa_k = osa_k_construct(1010101)
    Factors = [osa_k_factorize(osa_k, a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  # 0 になれば setwize
    st1 = set(factors)  # 重複しなければ pairwise
    pairwise = True
    for factors in Factors[1:]:
        st = set(factors)
        for f in st:
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
        st0 &= st
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

numba_compile([
    [solve, "void(i8,i8[:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    solve(N, A)

main()

Submission status: Accepted

Solution code:
from math import gcd
def fastprimes(n):
    p = [i for i in range(n+1)]
    for i in range(2,int(n**0.5+1)):
        if p[i] == i:
            for j in range(i,n+1,i):
                p[j] = i
    return p
p = fastprimes(10**6)
n = int(input())
a = list(map(int,input().split()))
c = [0]*10**6
g = 0
for i in a:
    g = gcd(g,i)
    b = {0}
    while p[i] != i:
        b.add(p[i])
        i //= p[i]
    b.add(p[i])
    for j in b:
        c[j] += 1
f = 1
for i in c[2:]:
    if i>1:
        f = 0
# print(c[0:100])
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import reduce
from math import gcd
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    if reduce(gcd, A) != 1:
        print("not coprime")
        return

    M = max(A)
    sieve = list(range(M + 1))
    sieve[0] = sieve[1] = INF
    for p in range(2, M + 1):
        if sieve[p] != p:
            continue
        for i in range(2 * p, M + 1, p):
            sieve[i] = min(sieve[i], p)

    used = set()
    for a in A:
        primes = set()
        while a > 1:
            p = sieve[a]
            primes.add(p)
            a //= p
        for p in primes:
            if p in used:
                print("setwise coprime")
                return
            used.add(p)

    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

n = int(input())
A = list(map(int, input().split()))

amax = max(A)
F  = arrayF(amax)

P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  max_count = max(max_count,sum(counts[i::i]))

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Accepted

Solution code:
def gcd(n,m):
    while n:
        m,n = n,m%n
    return m

N = int(input())
A = list(map(int,input().split()))

maxA = max(A)
B = [0]*(maxA+1)
for i in range(2,maxA+1):
    if B[i] == 0:
        B[i] = i
        for j in range(2*i,maxA+1,i):
            B[j] = i

soinsu = set()
a,b = 0,0

def pariwise():
    global N,A,soinsu,a,b
    for i in range(N):
        a = A[i]
        b = set()
        while a != 1:
            b.add(B[a])
            a //= B[a]
        for j in b:
            if j in soinsu:
                return False
            soinsu.add(j)
    return True

def setwise():
    global N,A,soinsu,a,b
    a = A[0]
    for i in range(1,N):
        a = gcd(a,A[i])
    return (a == 1)

if pariwise():
    print('pairwise coprime')
elif setwise():
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from math import gcd

N=int(input())
A=list(map(int,input().split()))

M=10**6

D=[-1]*(M+1)
D[0]=D[1]=1
for i in range(2,int(M**0.5)+1):
    if D[i]!=-1:
        continue
    for j in range(i*2,M+1,i):
        if D[j]==-1:
            D[j]=i

f=[False]*(M+1)

for x in A:
    l=[]
    while x>1:
        if f[x]==True:
            break
        if D[x]>1:
            l.append(D[x])
            x//=D[x]
        else:
            l.append(x)
            x=1
    else:
        for y in l:
            f[y]=True
        continue
    break
else:
    print('pairwise coprime')
    exit()

tmp=A[0]
for x in A[1:]:
    tmp=gcd(tmp,x)
    if tmp==1:
        print('setwise coprime')
        exit()
else:
    print('not coprime')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Accepted

Solution code:
import math
def eratos(n):
    isprime = [i for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == i:
            j = i
            while j <= n:
                if isprime[j] == j:
                    isprime[j] = i
                j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]
for ai in A:
    primes = {}
    while ai != 1:
        p = isprime[ai]
        primes[p] = 1
        ai //= p
    for p in primes.keys():
        count[p] += 1
max_c = max(count)
if max_c <= 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')