333
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...