yukicoder : No.313 π

無駄に頑張ってしまった…。
http://yukicoder.me/problems/686

問題

円周率が小数点以下20万桁まで与えられる。
ただし1桁だけ数字が誤っている。

誤っている数字を訂正せよ。

解法

正しい円周率について、0～9の登場回数を数えておき、入力と比較すればよい。

…自分は無駄にどの桁が誤っているか求めるコードを書いてしまった。
せっかくなので一応書いておく。

いわゆるチェックサムの考え方を適用する。
200000＋α個程度の素数を最初に計算しておく。
ここで11以上のk番目の素数をP(k)とする。

正しいπの小数第i位の値をd(i)としたとき、sum(d(i)*P(i))を覚えておこう。
幸いこの値は64bit符号付き整数で十分収まる。

入力値について同様にsum(d(i)*P(i))を求め、正しいπに対する値との差をとると、その値はどれかの素数の倍数になっている。
これによりどの桁が誤っていたか検出できる。

string S;
ll ret=0;
ll hoge=1187919047255;

const int prime_max = 3000000;
int NP,prime[300000],divp[prime_max];
map<int,int> M;

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>S;
	S=S.substr(0,1)+S.substr(2,200000);
	for(i=1;i<=200001;i++) ret += (S[i-1]-'0')*1LL*prime[i+5];
	
	ll dif=(hoge-ret);
	
	for(i=1;i<=200001;i++) if(dif % prime[i+5]==0) break;
	cout<<S[i-1]<<" "<<(char)(S[i-1]+dif/prime[i+5])<<endl;
	
}

まとめ

TT。