[질문] 방정식 gcd(a,x)=b 만족하는 해의 개수

[익명(49.167)]

f(a,b) 를

gcd(a,x)=b를 만족하는 정수 x의 개수 (1<=x<=n)

라고 하고

sigma a:1->n {sigma b:1->n { f(a,b) }} 의 값을

구하고 싶은데

이거 n^2 미만으로 가능함?

n은 졸라 작음

[메리체리(mrscherry)]

답이 n^2 아니냐

[익명(49.167)]

에디토리얼 보니까 나랑 좀 다른 접근인데 nlogn로 풀어놨길래 hoxy...? 내 풀이도 요로콤조로콤하면 되지 않을까 했는데 여윽시 망상이었나ㅜ

[메리체리(mrscherry)]

아니 sigma a:1->n {sigma b:1->n { f(a,b) }}=n^2 아님?

[익명(49.167)]

띠용 그런가여?

[메리체리(mrscherry)]

결국 gcd(a, x)=b인 a,b,x 쌍 개수인데 a x정해지면 b는 유일하잖아

[익명(49.167)]

사랑합니다