bdc8bb3e19 2015-05-13 kinaba: #include <iostream> bdc8bb3e19 2015-05-13 kinaba: #include <sstream> bdc8bb3e19 2015-05-13 kinaba: #include <iomanip> bdc8bb3e19 2015-05-13 kinaba: #include <vector> bdc8bb3e19 2015-05-13 kinaba: #include <string> bdc8bb3e19 2015-05-13 kinaba: #include <map> bdc8bb3e19 2015-05-13 kinaba: #include <set> bdc8bb3e19 2015-05-13 kinaba: #include <algorithm> bdc8bb3e19 2015-05-13 kinaba: #include <numeric> bdc8bb3e19 2015-05-13 kinaba: #include <iterator> bdc8bb3e19 2015-05-13 kinaba: #include <functional> bdc8bb3e19 2015-05-13 kinaba: #include <complex> bdc8bb3e19 2015-05-13 kinaba: #include <queue> bdc8bb3e19 2015-05-13 kinaba: #include <stack> bdc8bb3e19 2015-05-13 kinaba: #include <cmath> bdc8bb3e19 2015-05-13 kinaba: #include <cassert> bdc8bb3e19 2015-05-13 kinaba: #include <tuple> bdc8bb3e19 2015-05-13 kinaba: using namespace std; bdc8bb3e19 2015-05-13 kinaba: typedef long long LL; bdc8bb3e19 2015-05-13 kinaba: typedef complex<double> CMP; bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: bool is_prime(int p) bdc8bb3e19 2015-05-13 kinaba: { bdc8bb3e19 2015-05-13 kinaba: for(int q=2; q*q<=p; ++q) bdc8bb3e19 2015-05-13 kinaba: if(p%q==0) bdc8bb3e19 2015-05-13 kinaba: return false; bdc8bb3e19 2015-05-13 kinaba: return true; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: static const unsigned MODVAL = 1000000007; bdc8bb3e19 2015-05-13 kinaba: struct mint bdc8bb3e19 2015-05-13 kinaba: { bdc8bb3e19 2015-05-13 kinaba: unsigned val; bdc8bb3e19 2015-05-13 kinaba: mint():val(0){} bdc8bb3e19 2015-05-13 kinaba: mint(int x):val(x%MODVAL) {} bdc8bb3e19 2015-05-13 kinaba: mint(unsigned x):val(x%MODVAL) {} bdc8bb3e19 2015-05-13 kinaba: mint(LL x):val(x%MODVAL) {} bdc8bb3e19 2015-05-13 kinaba: }; bdc8bb3e19 2015-05-13 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } bdc8bb3e19 2015-05-13 kinaba: mint operator*(mint x, mint y) { return x*=y; } bdc8bb3e19 2015-05-13 kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: class PolynomialGCD { public: bdc8bb3e19 2015-05-13 kinaba: int gcd(string s) bdc8bb3e19 2015-05-13 kinaba: { bdc8bb3e19 2015-05-13 kinaba: mint ans = 1; bdc8bb3e19 2015-05-13 kinaba: for(int p=2; p<=s.size()+1; ++p) bdc8bb3e19 2015-05-13 kinaba: if(is_prime(p)) bdc8bb3e19 2015-05-13 kinaba: ans *= POW(p, howManyTimesAlwaysDivisibleByP(s, p)); bdc8bb3e19 2015-05-13 kinaba: return ans.val; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: int howManyTimesAlwaysDivisibleByP(const string& s, int p) bdc8bb3e19 2015-05-13 kinaba: { bdc8bb3e19 2015-05-13 kinaba: static const int INF = 0x7fffffff; bdc8bb3e19 2015-05-13 kinaba: int at_least = INF; bdc8bb3e19 2015-05-13 kinaba: for(int k=-p; k<=+p; ++k) { bdc8bb3e19 2015-05-13 kinaba: int cur = 0; bdc8bb3e19 2015-05-13 kinaba: for(int b=((k+p+p-1)/p-1)*p,i=s.size()-1-(b-k); i>=0; b+=p,i-=p) { bdc8bb3e19 2015-05-13 kinaba: int e = s[i]-'0'; bdc8bb3e19 2015-05-13 kinaba: if(b==0 && e) bdc8bb3e19 2015-05-13 kinaba: goto next; bdc8bb3e19 2015-05-13 kinaba: if(e) bdc8bb3e19 2015-05-13 kinaba: for(int bb=b; bb%p==0; bb/=p) bdc8bb3e19 2015-05-13 kinaba: cur+=e; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: at_least = min(at_least, cur); bdc8bb3e19 2015-05-13 kinaba: next:; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: return at_least; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: }; bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: // BEGIN CUT HERE bdc8bb3e19 2015-05-13 kinaba: #include <ctime> bdc8bb3e19 2015-05-13 kinaba: double start_time; string timer() bdc8bb3e19 2015-05-13 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } bdc8bb3e19 2015-05-13 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) bdc8bb3e19 2015-05-13 kinaba: { os << "{ "; bdc8bb3e19 2015-05-13 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) bdc8bb3e19 2015-05-13 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } bdc8bb3e19 2015-05-13 kinaba: void verify_case(const int& Expected, const int& Received) { bdc8bb3e19 2015-05-13 kinaba: bool ok = (Expected == Received); bdc8bb3e19 2015-05-13 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; bdc8bb3e19 2015-05-13 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } bdc8bb3e19 2015-05-13 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); bdc8bb3e19 2015-05-13 kinaba: #define END verify_case(_, PolynomialGCD().gcd(s));} bdc8bb3e19 2015-05-13 kinaba: int main(){ bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: CASE(0) bdc8bb3e19 2015-05-13 kinaba: string s = "111"; bdc8bb3e19 2015-05-13 kinaba: int _ = 6; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(1) bdc8bb3e19 2015-05-13 kinaba: string s = "00000"; bdc8bb3e19 2015-05-13 kinaba: int _ = 1; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(2) bdc8bb3e19 2015-05-13 kinaba: string s = "2014"; bdc8bb3e19 2015-05-13 kinaba: int _ = 16; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(3) bdc8bb3e19 2015-05-13 kinaba: string s = "31415926535"; bdc8bb3e19 2015-05-13 kinaba: int _ = 659897170; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: /* bdc8bb3e19 2015-05-13 kinaba: CASE(4) bdc8bb3e19 2015-05-13 kinaba: string s = ; bdc8bb3e19 2015-05-13 kinaba: int _ = ; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(5) bdc8bb3e19 2015-05-13 kinaba: string s = ; bdc8bb3e19 2015-05-13 kinaba: int _ = ; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: */ bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: // END CUT HERE