AtCoder版マスター・オブ・整数(最大公約数編)をPythonで実装してみる

このページはけんちょんさんによるAtCoder 版！マスター・オブ・整数 (最大公約数編)をPythonで実装して学ぶ記事になります。アルゴリズム等の詳しい内容はAtCoder 版！マスター・オブ・整数 (最大公約数編)をご覧ください。

問題1: ABC109 C – Skip

数直線上にN個の都市があり、i番目の都市は座標\(x_i\)にあります。
あなたの目的は、これら全ての都市を1度以上訪れることです。
あなたは、はじめに正整数 Dを設定します。
その後、あなたは座標 Xから出発し、以下の移動1,2を好きなだけ行います。

移動1:座標 yから座標y+Dに移動する
移動2: 座標yから座標y−Dに移動する
全ての都市を1度以上訪れることのできるDの最大値を求めてください。

#再帰
def gcd(a, b):
	if b==0:
		return a
	return gcd(b, a%b)
#ループ
def gcd(a,b):
  while b:
    a,b = b,a%b
  return abs(a)

def solve(x_list):
	ans=0
	for x in x_list:
		ans=gcd(ans, x)
	return ans

N, X = map(int, input().split())
x_list=list(abs(int(x)-X) for x in input().split())
print(gcd(0, 10)) #10になる
print(solve(x_list))

問題2: ABC109 C – Snack

パーティ来場者のためにお菓子を配りたい。パーティ参加人数は AA 人である可能性と、BB 人である可能性とがある。どちらの場合においても各参加者に配るお菓子の個数が均等になるようにしたい。
そのようなことが可能となるようなお菓子の個数の最小値を求めよ。


#解法1
A,B = map(int,input().split())
def gcd(a, b):
	if b==0:
		return a
	return gcd(b, a%b)
print(A*B//gcd(A,B))

#解法2
from fractions import gcd
A,B = map(int,read().split())
answer = A * B // gcd(A,B)
print(answer)

問題3: ABC118 C – Monsters Battle Royale

N体のモンスターが居て、それぞれ1,2,…,Nと番号付けられています。
はじめ、モンスターiの体力は\(A_i\)です。
以降、体力が1以上のモンスターを生きているモンスターと呼びます。
生きているモンスターが1体になるまで以下を繰り返します。
ランダムに1体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。
最後に生き残ったモンスターの最終的な体力の最小値を求めてください。


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

def gcd(a,b):
	while b:
		a, b = b, a%b
	return a


ans=0
for a in A:
	ans=gcd(ans, a)
print(ans)

問題4: 線分上の格子点の個数

平面上の2つの格子点\( (a_x, a_y), \ (b_x, b_y) \)が与えられる。
この２点を結ぶ線分上に何個の格子点があるか求めよ（両端を含まない）
制約: \(-10^9 \leq a_x, a_y, b_x, b_y \leq 10^9 \)


def gcd(a, b):
	while b:
		a, b = b, a%b
	return a
P=[]
for _ in range(2):
	x, y = map(int, input().split())
	P.append((x, y))

print(gcd(abs(P[0][0]-P[1][0]), abs(P[0][1]-P[1][1])) -1)

問題5: Yukicoder No.442 和と積

2つの正整数A,Bが与えられるので、和A+Bと積A×Bの最大公約数を求めてください。


A, B =map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a%b
	return a

g=gcd(A, B)
print(g * gcd(A/g + B/g, g))7 15

問題6: ABC060 B – Choose Integers

あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。どんなに大きな整数を選んでもよいですし、整数を5000兆個選んでもよいです。
ただし、選ぶ数はすべてAの倍数でなくてはいけません。また、少なくとも1つは整数を選ばなくてはいけません。
そして総和をBで割ったあまりがCとなるようにしたいです。こうなるように整数を選ぶことが出来るか判定してください。
出来るならば YES、そうでないならば NO を出力してください。


A, B , C = map(int, input().split())
def gcd(a, b):
	while b:
		a, b = b, a%b
	return a

if C%gcd(A,B)==0:
	print("YES")
else:
	print("NO")

問題7: AOJ 2610 Fast Division

0以上の整数Nが与えられる。
Nに対して、\(2^2 \cdots ^2\) (2がN個)より大きい最小の素数をpとおく。111…1(1がp−1個)をpで割ったあまりを求めよ。


#pを2と5以外の素数とするとき、あるレプユニット数が存在してpで割り切れる
N=int(input())
if N==0: #2^0=1<2=p, 1%2=1
	print(1)
elif N==1: #2^1=2<3=p, 11%3=2
	print(2)
elif N==2: #2^2=4<5=p, 1111%5=1
	print(1)
else:
	print(0)

問題8: TopCoder SRM 490 DIV1 Easy Starport

正の整数 N,Mが与えられる。
0,M,2M,…,(N−1)M0をNで割ったあまりの平均値を求めよ。
制約: \(1\leq N,M\leq 10^9\)

def gcd(a, b):
	while b:
		a, b = b, a%b
	return a

M, N = map(int, input().split())
print(gcd(N,M) * (N/gcd(M,N) -1)/2)

問題9: Educational Codeforces Round 81 D. Same GCDs

正の整数a,mが与えられる。
GCD(a,m)=GCD(a+x,m)
GCD(a,m)=GCD(a+x,m)
を満たす整数x(\( 0 \leq x < m \))の個数を求めよ。制約: \( 1 \leq a < m \leq 10^{10}\)

import scipy
a, m = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a%b
	return a

#https://swdrsker.hatenablog.com/entry/2017/06/22/182216
def euler(n):
    factors = sympy.factorint(n)
    rst = 1
    for i,j in factors.iteritems():
        rst *= (pow(i,j) - pow(i,j-1))
    return rst


print(euler(m/gcd(a,m)))