crt

中国剰余定理です。仕様は本家と同じです。入力のr,mはlistの形であって、len(r)=len(m)を要求します。返り値は(x,y)というtupleになっています。

注意：使用する際には、crtだけではなく、inv_gcd,inv_mod関数も同時にコピペしてください。

使用例

(https://atcoder.jp/contests/acl1/tasks/acl1_b)

def inv_gcd(a,b):
    # (中略)
def inv_mod(x,m):
    # (中略)
def crt(r,m):
    #(中略)
N=int(input())
def divide(n):
    res=[]
    i=1
    while(i*i<=n):
        if n%i==0:
            res.append(i)
            if i*i!=n:
                res.append(n//i)
        i+=1
    return res
ans=2*N
for b in divide(2*N):
    c=(2*N)//b
    tmp=crt([0,c-1],[b,c])
    if tmp==(0,0):
        continue
    x=tmp[0]
    if x==0:
        x=tmp[1]
    ans=min(x,ans)
print(ans)

floor-sum

sum_{i=0}^{n-1} floor((a*i+b)//m)を高速に求めるものです。

使用例

(https://atcoder.jp/contests/practice2/tasks/practice2_c)

def floor_sum(n,m,a,b):
    #(中略)
T=int(input())
for i in range(T):
    N,M,A,B=map(int,input().split())
    print(floor_sum(N,M,A,B))