#542272 (PyPy3) No.1200 お菓子配り-3

• 問題: No.1200 お菓子配り-3
• ユーザー: uni_python
• 提出日時: 2020-08-28 22:22:20
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 360 ms / 4,000 ms
• コード長: 3,551 bytes
• コンパイル時間: 242 ms
• コンパイル使用メモリ: 82,296 KB
• 実行使用メモリ: 80,336 KB
• 最終ジャッジ日時: 2024-11-20 22:35:23
• 合計ジャッジ時間: 6,041 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def main():
    mod=10**9+7
    S=I()
    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    def isPrimeMR(n):
        d = n - 1
        d = d // (d & -d)
        L = [2]
        for a in L:
            t = d
            y = pow(a, t, n)
            if y == 1: continue
            while y != n - 1:
                y = (y * y) % n
                if y == 1 or t == n - 1: return 0
                t <<= 1
        return 1
    def findFactorRho(n):
        m = 1 << n.bit_length() // 8
        for c in range(1, 99):
            f = lambda x: (x * x + c) % n
            y, r, q, g = 2, 1, 1, 1
            while g == 1:
                x = y
                for i in range(r):
                    y = f(y)
                k = 0
                while k < r and g == 1:
                    ys = y
                    for i in range(min(m, r - k)):
                        y = f(y)
                        q = q * abs(x - y) % n
                    g = gcd(q, n)
                    k += m
                r <<= 1
            if g == n:
                g = 1
                while g == 1:
                    ys = f(ys)
                    g = gcd(abs(x - ys), n)
            if g < n:
                if isPrimeMR(g): return g
                elif isPrimeMR(n // g): return n // g
                return findFactorRho(g)
    #[(p1,n1),(p2,n2),...]の形で返す
    def primeFactor(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k
        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret
    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    def divisors(N):
        pf = primeFactor(N)
        ret = [1]
        for p in pf:
            ret_prev = ret
            ret = []
            for i in range(pf[p]+1):
                for r in ret_prev:
                    ret.append(r * (p ** i))
        return sorted(ret)
    
    
    def calc(X,Y):
        diff=X-Y
        if diff==0:
            ans=0
            #A=1の場合，B+C=X=Y
            ans+=X-1
            
            #それ以外ならB*(A+1)=X=Y
            d=divisors(X)
            ans+=len(d)-1#(A+1)の部分がdの要素になれば良い，(A+1)は1になり得ない
            if X%2==0:# (A+1)=2 => A=1 をダブルカウントしている
                ans-=1
            return ans
        
        d=divisors(diff)
        ans=0
        for i in range(len(d)):
            A=d[i]+1
            Z=d[-1-i]
            if Y-Z>0:
                if (Y-Z)%(A+1)==0:
                    ans+=1
        return ans
        
    
    # X-Y=(B-C)*(A-1)
    for _ in range(S):
        x,y=MI()
        if y>x:
            x,y=y,x
        print(calc(x,y))
            
        
main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX