結果

問題 No.2125 Inverse Sum
コンテスト
ユーザー pitP
提出日時 2022-11-19 02:16:59
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,389 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 80,196 KB
最終ジャッジ日時 2024-09-20 06:10:13
合計ジャッジ時間 4,439 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#https://qiita.com/drken/items/3beb679e54266f20ab63
class Eratosthenes:
    def __init__(self,nmax):
        self._n = nmax
        self.isprime = [True] * (self._n+1)
        self.minfactor = [-1] * (self._n+1) #整数iを割り切る最小の素数
        self.mobius = [1] * (self._n+1) #メビウス関数

        #Eratosthenes O(Nlog(logN))
        self.isprime[0] = False
        self.isprime[1] = False
        for p in range(2,self._n+1):
            if not self.isprime[p]:
                continue

            self.minfactor[p] = p
            self.mobius[p] = -1

            for q in range(2*p,self._n+1,p):
                self.isprime[q] = False
                if self.minfactor[q] == -1:
                    self.minfactor[q] = p

                if (q//p) % p == 0 :
                    self.mobius[q] = 0
                else:
                    self.mobius[q] *= -1
    
    #素数判定,O(1)
    def judge_prime(self,n):
        return self.isprime[n]
    
    #素数列挙,O(N)
    #primes = [2,3,5...,n]
    def list_primes(self,n):
        primes = []
        for p in range(n+1):
            if self.isprime[p]:
                primes.append(p)
        return primes
    
    #nを高速素因数分解,O(logN)
    #ans = [(素因数,指数)...]
    def factorize(self,n):
        ans = []
        while n > 1:
            p = self.minfactor[n]
            e = 0
            while self.minfactor[n] == p:
                n //= p
                e += 1
            ans.append((p,e))
        return ans

    #高速約数列挙，O(nの約数の個数),
    #(約数の個数) <= 240(n<=10**6) , <= 1344(n<=10**9)
    def divisors(self,n,flag = True):
        ans = [1]
        facts = self.factorize(n)
        for p,e in facts:
            s = len(ans)
            for i in range(s):
                v = 1
                for _ in range(e):
                    v *= p
                    ans.append(ans[i]*v)
        if flag : #約数を昇順ソート
            ans.sort()
        return ans
    
    #mobius[1] = 1
    #nが素数pで二回以上割り切れる時mobius[n] = 0
    #mobius[n] = pow(-1,nの素数の種類)
    def my_mobius(self,n):
        return self.mobius[n]
    
class fast_zeta:#f -> F
    def __init__(self,f):
        self._f = f[:]
        self._n = len(f) - 1 #fが12個なら12
        er = Eratosthenes(self._n)
        for p in range(2,self._n+1):
            if not er.judge_prime(p):
                continue
            for k in range(self._n//p,0,-1):
                self._f[k] += self._f[k*p]
    
    def zeta_f(self,i):
        return self._f[i]
    
class fast_mobius:#F -> f
    def __init__(self,F):
        self._F = F[:]
        self._n = len(F) - 1 #fが12個なら12
        er = Eratosthenes(self._n)
        for p in range(2,self._n+1):
            if not er.judge_prime(p):
                continue
            for k in range(1,self._n//p+1):
                self._F[k] -= self._F[k*p]
    
    def mobius_f(self,i):
        return self._F[i]

def gcd_conv(f,g):
    N = max(len(f),len(g))
    F = [0] * (N+1)
    for i in range(len(f)):
        F[i] = f[i]

    G = [0] * (N+1)
    for i in range(len(g)):
        G[i] = g[i]

    H = [0] * (N+1)
    F = fast_zeta(F)
    G = fast_zeta(G)
    for i in range(1,N+1):
        H[i] = F.zeta_f(i) * G.zeta_f(i)
    
    H = fast_mobius(H)
    return H

def solve_gcd_conv():
    f = [-1,1,2,3,4,5,6,7,8,9,10,11,12]
    g = [-1,1,3,5,7,9,11,13,15,17,19,21,23]
    h = gcd_conv(f,g)
    for i in range(1,max(len(f),len(g))):
        print(i,h.mobius_f(i))

#AOJ_NTL_1_D
def solve_euler_func(N):
    F = [-1]
    for i in range(1,N+1):
        if N%i : F.append(0)
        else : F.append(N//i)
    fm = fast_mobius(F)
    print(fm.mobius_f(1))

def solve_abc206e():
    l,r = map(int,input().split())
    b = 0
    for x in range(max(l,2),r+1):
        b += r//x-1
    
    F = [-1]
    for i in range(1,r+1):
        c = r//i - (l-1)//i
        F.append(c*(c-1)//2)
    f = fast_mobius(F)
    a = F[1] - f.mobius_f(1)
    print(2*(a-b))

from math import gcd
p,q = map(int,input().split())
g = gcd(p,q)
p = p // g
q = q // g

q2 = q ** 2
nums = Eratosthenes(202020)

ans = []
for num in nums.divisors(q2):
	pn = num + q
	pm = q2 // num + q
	if (pn % p == 0) and (pm % p == 0):
		ans.append([pn // p ,pm // p])
ans.sort()
print(len(ans))
for l in ans:
	print(*l)
0