- 「秘密の数 a,b(1≦a≦b)を決める。SuさんにS=a+bを、PriさんにP=a*bを教える。Suさんが「PriさんはSが当てられないはず」と教えることで初めてPriさんはSを特定できる」
- といったことが起こりうるS in [A, B]の和を求めよ
- 1≦A≦B≦5,000,000
- Ps(S) ... Sに対応するPの候補 として
- PCanNotTellS(S) ... PriがSを特定できない として
- PCanNotTellS(S) == P=pq(1≦p≦q)と2通り以上で表せる for any P in Ps(S) ということであろう
- Ps(S) = {1*(S-1), 2*(S-2), ...}
- とりあえずどんなPでも1*Pと分割できるので、P=K*(P/K) (K≧2)とも表せる時は必ず複数通りで表せる。
- P=1*P の時は P が合成数のときだけ複数通りで表せる.
- ということで PCanNotTellS(S) == S-1が合成数
- ■「Suさんが「PriさんはSが当てられないはず」と教えることで初めてPriさんはSを特定できる」とは
- 上記の状況かつ, S に対応する P のうちどれかは, その P に対応する S のうち PCanNotTellS(S) なものが丁度1コある
- ぽいな
- とここまでクリアじゃないけどとりあえずこんな感じでシミュレーションを書いてみよう
- ていうか S に対応する P ってめっちゃあるじゃん
- ループが深くなって何をしてんのかよく分からなくなってるうちに終了。
- S に対応する P は 1*(S-1), 2*(S-2), ... と沢山あるけど P = 1*(S-1) に対してだけ何か判定してるように見える
- PCanNotTellS と同様に 2*(S-2) 以降は常に「PCanNotTellS(S) なものが丁度1コ」じゃないのかもしれん
- S に対応する P として K*(S-K) (K≧2)を考えると, その P を P = 1*K(S-K) = K*(S-K) と分けることができて
- 対応する S としては 1+K(S-K) と K+(S-K) があることになる. そのどちらも
- 「1+K(S-K)-1は合成数」, 「K+(S-K)-1は合成数 (→S-1が合成数という前提から)」を満たすので K≧2の場合は丁度1コになりえない
- となるので、P=1*(S-1) だけについて「PCanNotTellS(S) なものが丁度1コ」かどうか考えればいい.
- となんとか捻り出せた
- P=S-1 に対応する S = {p+P/p, 1≦p≦P/p} のうち p+P/p-1 が合成数のやつが 1 コかどうか計算すればいいので
- ありうる p を全探索しつつ p+P/p-1 が合成数かどうかをカウントして
- S in [A, B] のうち S-1が合成数 && カウント[S-1]==1のものの和を求めると終了
- ということになった。
- 篩が O(NloglogN), 調和数がO(logN)なので
- 全体で O(NlogN)
- accepted in practice room
- I hate math yay
class SumAndProductPuzzle {
public:
long long getSum(int A, int B) {
const int N = 5000000;
vector<bool> isp(N+1, true);
RANGE(p, 2, sqrt(N+1)+2) if(isp[p])for(int q=p*2;q<N+1;q+=p) isp[q]=false;
vector<int> cnt(N+1);
RANGE(p, 1, N+1) RANGE(q, p, N/p+1) if(!isp[p+q-1]) cnt[p*q]++;
ll ans=0;
RANGE(S, A, B+1) if(!isp[S-1] && cnt[S-1]==1) ans+=S;
return ans;
}
};
