naoya_t@topcoder

SRM466 Easy: LotteryCheating

過去問 | 04:10 |

• 約数の個数が奇数 = 平方数
  • 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