結果

問題 No.261 ぐるぐるぐるぐる！あみだくじ！
コンテスト
ユーザー titia
提出日時 2026-07-22 03:36:29
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 78 ms / 5,000 ms
+ 843µs
コード長 2,258 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 230 ms
コンパイル使用メモリ 95,984 KB
実行使用メモリ 83,840 KB
最終ジャッジ日時 2026-07-22 03:36:35
合計ジャッジ時間 5,382 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

def lcm(x,y):
    return x*y//gcd(x,y)

N=int(input())
K=int(input())

A=list(range(N+1))

for i in range(K):
    x,y=map(int,input().split())
    A[x],A[y]=A[y],A[x]


# UnionFind

Group = [i for i in range(N+1)] # グループ分け
Nodes = [1]*(N+1) # 各グループのノードの数

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

for i in range(N+1):
    Union(i,A[i])

LIST=[[] for i in range(N+1)]

for i in range(N+1):
    X=[i]

    while True:
        if A[X[-1]]==i:
            break
        X.append(A[X[-1]])

    LIST[i]=X

# 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す.
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)
    q,r=divmod(a,b)

    if r==0:
        return bxy,b # a*bxy[0]+b*bxy[1]=b
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.
    return Ext_Euc(b,r,bxy,rxy)

# 中国剰余定理（拡張ユークリッドの互除法を使う）
def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbのときN=k mod(lcm(ma,mb))なるk,lcm(ma,mb)を返す.
    (p,q),d=Ext_Euc(ma,mb)
    if (a-b)%d!=0:
        return -1 # 解がないとき-1を出力
    return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//d


Q=int(input())

for tests in range(Q):
    B=[0]+list(map(int,input().split()))

    a=0
    ma=1

    flag=1

    for i in range(1,N+1):
        x=A[i]
        y=B[i]

        if y in LIST[x]:
            b=LIST[x].index(y)
            mb=len(LIST[x])

            c=Chirem(a,ma,b,mb)

            if c==-1:
                flag=0
                break
            else:
                a,ma=c
                

            
        else:
            flag=0
            break

    #print(a,ma,flag)

    if flag==0:
        print(-1)
    else:
        print(a+1)
0