Yuki 313 π ( Hash )

No.313 π - yukicoder
間違ってる位置を知らなくていいので、愚直に 0 ~ 9 それぞれの登場回数を比較すればいい。
しかし素数を base にして hash すると間違ってる位置がわかる。
kmjp.hatenablog.jp
素数は 10 以上のだけを使うのに注意。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

signed main(){
  vector< int > np( ( int ) 1e7 );
  vector< int > pt;
  for( int i = 2; pt.size() < ( int ) 2e5 + 1; ++i )
    if( not np[ i ] ){
      if( i > 9 )
        pt.emplace_back( i );
      for( int j = i + i; j < ( int ) 1e7; j += i )
        np[ j ] = 1;
    }

  /*
  string pi; cin >> pi;
  pi[ 0 ] = '3';
  ll hoge = 0LL;
  for( int i = 0, p = 0; i < pi.size(); ++i ){
    if( pi[ i ] == '.' ) continue;
    hoge += 1LL * pt[ p ] * ( pi[ i ] - '0' );
    ++p;
  }
  cout << hoge << endl;
  assert( hoge == 1187894336729LL );
  */

  const ll hoge = 1187894336729LL;
  
  string S; cin >> S;
  ll foo = 0LL;
  for( int i = 0, p = 0; i < S.size(); ++i ){
    if( S[ i ] == '.' ) continue;
    foo += 1LL * pt[ p ] * ( S[ i ] - '0' );
    ++p;
  }
  ll diff = foo - hoge;
  for( int i = 0; i < pt.size(); ++i )
    if( abs( diff ) % pt[ i ] == 0 ){
      int x = i > 0 ? i + 1 : i;
      cout << S[ x ] << " " << ( char ) ( S[ x ] - diff / pt[ i ] ) << endl;
      exit( 0 );
    }

  return 0;
}