7e18a763ef 2013-01-29 kinaba: #include <iostream> 7e18a763ef 2013-01-29 kinaba: #include <sstream> 7e18a763ef 2013-01-29 kinaba: #include <iomanip> 7e18a763ef 2013-01-29 kinaba: #include <vector> 7e18a763ef 2013-01-29 kinaba: #include <string> 7e18a763ef 2013-01-29 kinaba: #include <map> 7e18a763ef 2013-01-29 kinaba: #include <set> 7e18a763ef 2013-01-29 kinaba: #include <algorithm> 7e18a763ef 2013-01-29 kinaba: #include <numeric> 7e18a763ef 2013-01-29 kinaba: #include <iterator> 7e18a763ef 2013-01-29 kinaba: #include <functional> 7e18a763ef 2013-01-29 kinaba: #include <complex> 7e18a763ef 2013-01-29 kinaba: #include <queue> 7e18a763ef 2013-01-29 kinaba: #include <stack> 7e18a763ef 2013-01-29 kinaba: #include <cmath> 7e18a763ef 2013-01-29 kinaba: #include <cassert> 7e18a763ef 2013-01-29 kinaba: using namespace std; 7e18a763ef 2013-01-29 kinaba: typedef long long LL; 7e18a763ef 2013-01-29 kinaba: typedef long double LD; 7e18a763ef 2013-01-29 kinaba: typedef complex<LD> CMP; 7e18a763ef 2013-01-29 kinaba: 7e18a763ef 2013-01-29 kinaba: class TheSquareRootDilemma { public: 7e18a763ef 2013-01-29 kinaba: int countPairs(int N, int M) 7e18a763ef 2013-01-29 kinaba: { 7e18a763ef 2013-01-29 kinaba: static const int X = 279; 7e18a763ef 2013-01-29 kinaba: vector<bool> isp(X+1, true); 7e18a763ef 2013-01-29 kinaba: vector<int> ps; 7e18a763ef 2013-01-29 kinaba: for(int p=2; p<=X; ++p) 7e18a763ef 2013-01-29 kinaba: if( isp[p] ) { 7e18a763ef 2013-01-29 kinaba: ps.push_back(p); 7e18a763ef 2013-01-29 kinaba: for(int q=p+p; q<=X; q+=p) 7e18a763ef 2013-01-29 kinaba: isp[q] = false; 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: 7e18a763ef 2013-01-29 kinaba: map<vector<int>, int> AA; 7e18a763ef 2013-01-29 kinaba: for(int A=1; A<=N; ++A) 7e18a763ef 2013-01-29 kinaba: { 7e18a763ef 2013-01-29 kinaba: int x = A; 7e18a763ef 2013-01-29 kinaba: vector<int> v; 7e18a763ef 2013-01-29 kinaba: for(int i=0; i<ps.size(); ++i) { 7e18a763ef 2013-01-29 kinaba: int p = ps[i]; 7e18a763ef 2013-01-29 kinaba: int k = 0; 7e18a763ef 2013-01-29 kinaba: while(x%p==0) {k++; x/=p;} 7e18a763ef 2013-01-29 kinaba: v.push_back(k&1); 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: if(x==1) 7e18a763ef 2013-01-29 kinaba: AA[v]++; 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: 7e18a763ef 2013-01-29 kinaba: int result = 0; 7e18a763ef 2013-01-29 kinaba: for(int B=1; B<=M; ++B) 7e18a763ef 2013-01-29 kinaba: { 7e18a763ef 2013-01-29 kinaba: int x = B; 7e18a763ef 2013-01-29 kinaba: vector<int> v; 7e18a763ef 2013-01-29 kinaba: for(int i=0; i<ps.size(); ++i) { 7e18a763ef 2013-01-29 kinaba: int p = ps[i]; 7e18a763ef 2013-01-29 kinaba: int k = 0; 7e18a763ef 2013-01-29 kinaba: while(x%p==0) {k++; x/=p;} 7e18a763ef 2013-01-29 kinaba: v.push_back(k&1); 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: if(x==1) 7e18a763ef 2013-01-29 kinaba: result += AA[v]; 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: return result; 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: }; 7e18a763ef 2013-01-29 kinaba: 7e18a763ef 2013-01-29 kinaba: // BEGIN CUT HERE 7e18a763ef 2013-01-29 kinaba: #include <ctime> 7e18a763ef 2013-01-29 kinaba: double start_time; string timer() 7e18a763ef 2013-01-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 7e18a763ef 2013-01-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 7e18a763ef 2013-01-29 kinaba: { os << "{ "; 7e18a763ef 2013-01-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 7e18a763ef 2013-01-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 7e18a763ef 2013-01-29 kinaba: void verify_case(const int& Expected, const int& Received) { 7e18a763ef 2013-01-29 kinaba: bool ok = (Expected == Received); 7e18a763ef 2013-01-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 7e18a763ef 2013-01-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 7e18a763ef 2013-01-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 7e18a763ef 2013-01-29 kinaba: #define END verify_case(_, TheSquareRootDilemma().countPairs(N, M));} 7e18a763ef 2013-01-29 kinaba: int main(){ 7e18a763ef 2013-01-29 kinaba: 7e18a763ef 2013-01-29 kinaba: CASE(0) 7e18a763ef 2013-01-29 kinaba: int N = 2; 7e18a763ef 2013-01-29 kinaba: int M = 2; 7e18a763ef 2013-01-29 kinaba: int _ = 2; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: CASE(1) 7e18a763ef 2013-01-29 kinaba: int N = 10; 7e18a763ef 2013-01-29 kinaba: int M = 1; 7e18a763ef 2013-01-29 kinaba: int _ = 3; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: CASE(2) 7e18a763ef 2013-01-29 kinaba: int N = 3; 7e18a763ef 2013-01-29 kinaba: int M = 8; 7e18a763ef 2013-01-29 kinaba: int _ = 5; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: CASE(3) 7e18a763ef 2013-01-29 kinaba: int N = 100; 7e18a763ef 2013-01-29 kinaba: int M = 100; 7e18a763ef 2013-01-29 kinaba: int _ = 310; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: CASE(4) 7e18a763ef 2013-01-29 kinaba: int N = 77777; 7e18a763ef 2013-01-29 kinaba: int M = 77777; 7e18a763ef 2013-01-29 kinaba: int _ = -1; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: /* 7e18a763ef 2013-01-29 kinaba: CASE(5) 7e18a763ef 2013-01-29 kinaba: int N = ; 7e18a763ef 2013-01-29 kinaba: int M = ; 7e18a763ef 2013-01-29 kinaba: int _ = ; 7e18a763ef 2013-01-29 kinaba: END 7e18a763ef 2013-01-29 kinaba: */ 7e18a763ef 2013-01-29 kinaba: } 7e18a763ef 2013-01-29 kinaba: // END CUT HERE