333

 avatar
unknown
python
2 years ago
1.1 kB
8
Indexable


from sys import stdin
from math import sqrt, floor, ceil
input = stdin.readline
M, b = map(int,input().split())

def gcd(a,b):
    if b == 0:
        return a 
    return gcd(b,a%b)


def factors(n:int):
    ret = [] 
    sqrtn = ceil(sqrt(n))+1
    if n%2==0:
        ret.append(2)
        while(n%2==0):
            n//=2
        
    for i in range(3,sqrtn,2):
        if(n%i==0):
            ret.append(i)
            while(n%i==0):
                n//=i
    
    if(n>2):
        ret.append(n)
    return ret 

def totient(n, primes:list[int]):
    ret = 1
    for prime in primes:
        ret *= (n-n//prime)
        n//= prime
    return ret 

# 12 => 12(1-1/3)(1-1/2)=  4 (2-1

# 1 2 M : 3 b : 4 
ret = 0
for m in range(2,M+1):
    m_factors = factors(m)

    ret += 2*totient(m,m_factors)-1 # good 
    # 1. euler phi gcd(a,m) = 1 
    # ret += euler(phi(m))
    # 2. gcd(a,m) != 1 
    # if gcd(a,m)
    # if gcd(a,m)==1: 
    # 약수 
    for factor in m_factors:
        tmp = gcd(factor%m,m)
        B = b % m
        if B%(gcd(factor, m)) == 0:
            ret += M//m
        else:
            continue
print(ret)
Editor is loading...