問題一覧 > 通常問題

No.3690 Only One

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 51
作問者 : Unbakedbread / テスター : Tamiji153
お気に入りにしたユーザー ProblemId : 13819 / 自分の提出
問題文最終更新日: 2026-08-28 01:01:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
μ関数入門コース (順位表) の他の問題:

Problem Statement

You are given positive integers $A,B$.

Find the sum of $\mu(d)$ over all integers $d$ that are positive common divisors of $A$ and $B$.

What is $\mu(N)$? (click to expand) For a positive integer $N$, the value of $\mu(N)$ is defined as follows.
  • If $N=1$, then $\mu(N)=1$.
  • If $N$ is divisible by the square of some prime, then $\mu(N)=0$.
  • If $N$ is equal to a product of $K$ distinct primes, then $\mu(N)=(-1)^K$.

Constraints

  • $A,B$ are integers between $1$ and $10^{18}$, inclusive.

Input

$A\ B$

Output

Output the answer.

Sample

Sample 1
Input
24 60
Output
0

The positive common divisors of $24$ and $60$ are the following $6$ numbers: $1,2,3,4,6,12$.

Therefore, the answer is $\mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(6)+\mu(12)=1-1-1+0+1+0=0$.

Sample 2
Input
31 13
Output
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。