Joseph's Problem(1)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2800
いつの間にかcolunさんとushiodaさんによって変態的な記録が生み出されています。私もちょっと削ってみましたが、遠く及ばず。すごいですなぁ・・・。
さて、この手の問題を考える時、私は大体同じような手法で考えます。それは、定義通りに計算して、その過程を詳しく列挙する方法。で、しばらくデータをにらめっこしながら規則性を見つけます。
というわけで、こんなコードを書いてみました。
main(s,i,n,k){
s=0;
scanf("%d%d",&n,&k);
printf("n: %d, k: %d\n",n,k);
for(i=1;i<=n;++i){
printf("i:%3d, k/i:%3d, k%%i:%3d\n",i,k/i,k%i);
s+=k%i;
}
printf("ans: %d\n",s);
}n回のループなので、カウンタiと、k mod iは必ず書きます。あとは、気になる値。このコードを実行してみます。とりあえず、入力はサンプルの通りでやってみましょう。
n: 5, k: 3 i: 1, k/i: 3, k%i: 0 i: 2, k/i: 1, k%i: 1 i: 3, k/i: 1, k%i: 0 i: 4, k/i: 0, k%i: 3 i: 5, k/i: 0, k%i: 3 ans: 7
値が小さすぎてよくわかりませんが、とりあえず、iがkより大きくなるとk%i==kなのが確認できます。知りたいのはその前の部分。もう少し大きな値で調べてみます。
n: 90, k: 85 i: 1, k/i: 85, k%i: 0 i: 2, k/i: 42, k%i: 1 i: 3, k/i: 28, k%i: 1 i: 4, k/i: 21, k%i: 1 i: 5, k/i: 17, k%i: 0 i: 6, k/i: 14, k%i: 1 i: 7, k/i: 12, k%i: 1 i: 8, k/i: 10, k%i: 5 i: 9, k/i: 9, k%i: 4 i: 10, k/i: 8, k%i: 5 i: 11, k/i: 7, k%i: 8 i: 12, k/i: 7, k%i: 1 i: 13, k/i: 6, k%i: 7 i: 14, k/i: 6, k%i: 1 i: 15, k/i: 5, k%i: 10 i: 16, k/i: 5, k%i: 5 i: 17, k/i: 5, k%i: 0 i: 18, k/i: 4, k%i: 13 i: 19, k/i: 4, k%i: 9 i: 20, k/i: 4, k%i: 5 i: 21, k/i: 4, k%i: 1 i: 22, k/i: 3, k%i: 19 i: 23, k/i: 3, k%i: 16 i: 24, k/i: 3, k%i: 13 i: 25, k/i: 3, k%i: 10 i: 26, k/i: 3, k%i: 7 i: 27, k/i: 3, k%i: 4 i: 28, k/i: 3, k%i: 1 i: 29, k/i: 2, k%i: 27 i: 30, k/i: 2, k%i: 25 i: 31, k/i: 2, k%i: 23 i: 32, k/i: 2, k%i: 21 i: 33, k/i: 2, k%i: 19 i: 34, k/i: 2, k%i: 17 i: 35, k/i: 2, k%i: 15 i: 36, k/i: 2, k%i: 13 i: 37, k/i: 2, k%i: 11 i: 38, k/i: 2, k%i: 9 i: 39, k/i: 2, k%i: 7 i: 40, k/i: 2, k%i: 5 i: 41, k/i: 2, k%i: 3 i: 42, k/i: 2, k%i: 1 i: 43, k/i: 1, k%i: 42 i: 44, k/i: 1, k%i: 41 i: 45, k/i: 1, k%i: 40 i: 46, k/i: 1, k%i: 39 i: 47, k/i: 1, k%i: 38 i: 48, k/i: 1, k%i: 37 i: 49, k/i: 1, k%i: 36 i: 50, k/i: 1, k%i: 35 i: 51, k/i: 1, k%i: 34 i: 52, k/i: 1, k%i: 33 i: 53, k/i: 1, k%i: 32 i: 54, k/i: 1, k%i: 31 i: 55, k/i: 1, k%i: 30 i: 56, k/i: 1, k%i: 29 i: 57, k/i: 1, k%i: 28 i: 58, k/i: 1, k%i: 27 i: 59, k/i: 1, k%i: 26 i: 60, k/i: 1, k%i: 25 i: 61, k/i: 1, k%i: 24 i: 62, k/i: 1, k%i: 23 i: 63, k/i: 1, k%i: 22 i: 64, k/i: 1, k%i: 21 i: 65, k/i: 1, k%i: 20 i: 66, k/i: 1, k%i: 19 i: 67, k/i: 1, k%i: 18 i: 68, k/i: 1, k%i: 17 i: 69, k/i: 1, k%i: 16 i: 70, k/i: 1, k%i: 15 i: 71, k/i: 1, k%i: 14 i: 72, k/i: 1, k%i: 13 i: 73, k/i: 1, k%i: 12 i: 74, k/i: 1, k%i: 11 i: 75, k/i: 1, k%i: 10 i: 76, k/i: 1, k%i: 9 i: 77, k/i: 1, k%i: 8 i: 78, k/i: 1, k%i: 7 i: 79, k/i: 1, k%i: 6 i: 80, k/i: 1, k%i: 5 i: 81, k/i: 1, k%i: 4 i: 82, k/i: 1, k%i: 3 i: 83, k/i: 1, k%i: 2 i: 84, k/i: 1, k%i: 1 i: 85, k/i: 1, k%i: 0 i: 86, k/i: 0, k%i: 85 i: 87, k/i: 0, k%i: 85 i: 88, k/i: 0, k%i: 85 i: 89, k/i: 0, k%i: 85 i: 90, k/i: 0, k%i: 85 ans: 1673
これくらいならよくわかりますが、所々に等差数列が現れています。しかもその時の公差は-k/iで、簡単に求める事も可能ですね。最初の方は相変わらずよくわかりませんが、結局は初項がk%i, 項数が1と考えれば、問題なく計算できますし、最後のi>kのところも-k/i==0が公差と考えるのであれば同じ様に等差数列として計算する事が可能です。
