- 2008-12-14 (日) 0:07
- Imos Contest
The 1st Imos Contestは無事に終了いたしました．参加者の皆様お疲れ様でした．結果についてはWeb上にもあがっていますが，時間外参加の人もいたりなのでそのあたりを併合して後々にOUCPCのページに載せたいと思います．
あと問題を放っとくのもどうかと思うので何度かに分けて解説をしていこうと思います．
Problem A: Extended RSA
Overview
素数bと正の整数c,dが与えられた時に，ab≡c(mod 2d)を満たす素数aを見つける．
Comment
eb≡c(mod 2d)を満たすeをまず見つける．その後，aの候補はe+k2dのみとなるので，その条件を満たす素数を探せば良い．今回以下のコードでは満たすeを見つける方法をO(logN)にした(実際には2dまでしか要求はされていない)．その後素数判定はO(√N)で行っている．
001: #include <stdio.h>
002: typedef long long ll;
003:
004: int main() {
005: int b, c, d;
006: freopen("A.in", "r", stdin);
007: while (scanf("%d%d%d", &b, &c, &d), b) {
008: // seek a for ab=c(mod 2^d)
009: ll base = 0;
010: for (int i = 1; i <= d; i++)
011: if ((base * b ^ c) & ((1 << i) - 1)) base |= 1 << (i - 1);
012: // seek a prime
013: do {
014: // 1 is an exception
015: int isprime = (base != 1);
016: // check whether it is prime or not.
017: for (int i = 2; i * i <= base; i++)
018: if (base % i == 0) { isprime = false; break; }
019: // if it is prime, break
020: if (isprime) break;
021: // next number a
022: base += 1 << d;
023: } while (1);
024: // output a
025: printf("%d\n", base);
026: }
027: return 0;
028: }
002: typedef long long ll;
003:
004: int main() {
005: int b, c, d;
006: freopen("A.in", "r", stdin);
007: while (scanf("%d%d%d", &b, &c, &d), b) {
008: // seek a for ab=c(mod 2^d)
009: ll base = 0;
010: for (int i = 1; i <= d; i++)
011: if ((base * b ^ c) & ((1 << i) - 1)) base |= 1 << (i - 1);
012: // seek a prime
013: do {
014: // 1 is an exception
015: int isprime = (base != 1);
016: // check whether it is prime or not.
017: for (int i = 2; i * i <= base; i++)
018: if (base % i == 0) { isprime = false; break; }
019: // if it is prime, break
020: if (isprime) break;
021: // next number a
022: base += 1 << d;
023: } while (1);
024: // output a
025: printf("%d\n", base);
026: }
027: return 0;
028: }
- Newer: レポートの山
- Older: The 1st Imos Contest が明日に迫りました
Comments:2
- rsujskf 08-12-14 (日) 15:42
-
コンテストお疲れ様でした．なかなか面白い問題達で楽しかったですよー．
問題文読み落としてるだけだったら申し訳ないのですが…，
A問題，入力b=2, c=18, d=6 (2^d=64) に対して出力は41となるべきだと思うのですが，そのコードだと無限ループになりませんか?
まぁ，ジャッジ入力にb=2とか怪しいケースは見当たらなかったですけど． - imos 08-12-15 (月) 0:43
-
ありがとうございますー．
おっと本当ですねー，実はこのRSAに埋めるということは実際にやろうとしていて，その実用の時のコードのイメージのまま作ってしまったのでまずかったですねー．
一人だけで全部やるというのはかなり大変だというのを今回実感したところですが，たぶん次もめげずにがんばろうと思います（ぁ．
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2008/12/the-1st-imos-contest-ends/trackback/
- Listed below are links to weblogs that reference
- The 1st Imos Contest 終了 from 超現実いもす(imos)の日記