問題一覧 > 通常問題

No.826 連絡網

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 181
作問者 : PachicobuePachicobue / テスター : koprickykopricky
10 ProblemId : 2982 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-04 00:28:10

問題文

青木さんは集合住宅街であるY町に住んでいます。
Y町には青木くんを含めて$N$人が住んでおり、それぞれ家$1$,家$2$,...,家$N$に1人ずつ住んでいます。青木くんは家$P$に住んでいます。

元々Y町は連絡網が発達しており、任意の家$i,j\ (1\le i\lt j \le N)$は直接電話線で繋がれており、双方向に連絡を取ることが出来ました。
しかし$i$と$j$が互いに素であるような家$i,j\ (1\le i\lt j \le N)$の人は例外なく仲が悪く、家$i,j$を直接結ぶ電話線を切ってしまいました。それ以外の家同士は今でも電話線で結ばれています。

ある日青木くんはY町に関する秘密の情報を握りました。その時点では他の住民はその情報を知りません。
Y町の住民は全員例外なく口が軽いので、情報を知ったら直ちに電話で他の住民に秘密を拡散します。電話線でつながっていない家の人には伝えられません。
最終的に情報を知ることができる住民は、青木くん自身を含めて何人いるか求めて下さい。

Y町の住人は自宅の外へは決して出ず、またY町の住人以外と一切連絡を取らないので秘密の情報はY町の住人同士の電話でのやり取り以外で拡散されることは無いものとします。

入力

$N\ P$

一行目にはY町の住人の数$N$と、青木くんの家番号$P$が空白区切りで与えられます。

制約
  • $1 \le N \le 10^6$
  • $1 \le P \le N$
  • 入力は全て整数である。

出力

拡散された秘密の情報を知ることのできる、Y町の住人の数を一行で出力しなさい。
最後に改行して下さい。

サンプル

サンプル1
入力
6 4
出力
4

残っている電話線は以下の黒線で示された辺のみで、 青木くんの家から(直接的 or 間接的に)情報が伝達できる家は青色の家です。

サンプル2
入力
17 13
出力
1

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