Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-04

SRM466 Easy: LotteryCheating

| 04:10 | SRM466 Easy: LotteryCheating - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM466 Easy: LotteryCheating - naoya_t@topcoder SRM466 Easy: LotteryCheating - naoya_t@topcoder のブックマークコメント

  • 約数の個数が奇数 = 平方数
    • n = p1^a1 * p2^a2 * ... * pn^an のとき
    • 約数の個数は (a1+1)(a2+1)..(an+1)
    • これが奇数ということはa1...anはすべて偶数
    • だったら n={(p1^(a1/2))(p2^(a2/2))..(pn^(an/2))}^2
  • 0≦n≦9999999999 なので0≦x≦99999の二乗を調べればよい
  • それぞれの平方数と比較して、何文字異なるか
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class LotteryCheating {
public:
  int minimalChange(string ID) {
    int n=sz(ID);
    ll nmax=1; rep(i,n) nmax*=10; nmax--;

    int ch=n+1;
    for(ll i=0;i<100000;i++){
      ll ii=i*i; if (ii > nmax) break;
      string iis(n,'0');
      rep(j,n) { iis[n-1-j] = '0' + (ii%10); ii/=10; }
      int cn=0;
      rep(j,n) {
        if (iis[j]!=ID[j]) cn++;
      }
      ch = min(cn,ch);
    }
    return ch;
  }
};
  • passed system test
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100404