Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2010-07-10

SRM 400 StrongPrimePower

| 01:11 |  SRM 400 StrongPrimePower - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  SRM 400 StrongPrimePower - yowa の TopCoder 日記

問題

与えられた文字列 n が、素数のべき乗(の十進表記)だったら素数 p と指数 q を返す(ただし q > 2)。そうでなければ、空 vector を返す。

やったこと

n は 10**18 以下なので、64bitに収まる。で、64bit整数の型の名前は何だ。

int64_t とゆーのがあったのでこれ使う。

vector とか string って、対応したヘッダを include しなきゃ使えないのか(考えたら当たり前だ)。

std::vector とか書くのか。めんどい。なんか using namespace std; というおまじないを書けばいいらしい。

文字列→64bit整数の変換がわからない。ので for ループで1文字ずつデコード。

「割り切れる最小の素数 p を見つけて、それで繰り返し割って、割り切れたらおk」という方針でコードを書く。

p は 2 と 3 以上の奇数をなめることにする。n<10**18 で q>2 なので、10**9 までなめればよし。

テスト。999999874000003979 (= 999999937**2) が終わらない。約 10**9/2 回のループは無茶か。

q>3 と q==2 に分けるか。

10**6 までなめて、割り切れるなら今まで通り。そうでなければ (int)sqrt(n) の2乗が n に一致するか調べる。

合成数の2乗が誤爆しないかな?

n == c**2 で c が合成数ならば、c<10**9 だから c は 10**4.5 以下の素因数を持つので、こっちの分岐には来ない。

テスト。おkっぽい。

System Test の最終確認はどうすればいいのだろう。

エディタ画面で Save して Compile して Submit して、アリーナ画面で Practice Options → Run System Test して、Status が緑色で表示されればいいのかな?

コード

#include <vector>
#include <string>
#include <cmath>
using namespace std;
class StrongPrimePower {
public:
  vector<int> baseAndExponent(string n) {
    vector<int> ret;

    uint64_t num = 0;
    for (int i=0; i<n.size(); i++) {
      num = num*10 + n[i]%16;
    }

    const int p_max = 1000000;
    int prime;
    if (num%2 == 0)
      prime = 2;
    else {
      for (prime=3; prime<p_max; prime+=2) {
	if (num%prime == 0)
	  break;
      }
    }

    int q;
    uint64_t tmp = num;
    for (q=0; tmp>=prime && tmp%prime == 0; q++)
      tmp /= prime;

    if (tmp == 1 && q > 1) {
      ret.push_back(prime);
      ret.push_back(q);
    } else if (prime >= p_max) {
      // checking square of large prime
      uint64_t x;
      x = (uint64_t)sqrt(num);
      if (num == x*x) {
	ret.push_back(x);
	ret.push_back(2);
      }
    }

    return ret;
  }
};