Overview
| SHA1 Hash: | 2c9a31df161c398f10f9304cfd52703bd6df3201 |
|---|---|
| Date: | 2015-06-20 00:04:34 |
| User: | kinaba |
| Comment: | 661 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/661-U/1A.cpp version [65608fb9e8ac2cf6]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class MissingLCM { public: > 23 int getMin(int N) > 24 { > 25 int M = N+1; > 26 vector<bool> isp(N+1, true); > 27 for(int p=2; p<=N; ++p) > 28 if( isp[p] ) { > 29 for(LL q=p; q<=N; q*=p) > 30 M = max<int>(M, (N/q+1)*q); > 31 for(int q=p+p; q<=N; q+=p) > 32 isp[q] = false; > 33 } > 34 return M; > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const int& Expected, const int& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, MissingLCM().getMin(N));} > 52 int main(){ > 53 > 54 CASE(0) > 55 int N = 1; > 56 int _ = 2; > 57 END > 58 CASE(1) > 59 int N = 2; > 60 int _ = 4; > 61 END > 62 CASE(2) > 63 int N = 3; > 64 int _ = 6; > 65 END > 66 CASE(3) > 67 int N = 4; > 68 int _ = 8; > 69 END > 70 CASE(4) > 71 int N = 5; > 72 int _ = 10; > 73 END > 74 CASE(5) > 75 int N = 42; > 76 int _ = 82; > 77 END > 78 CASE(6) > 79 int N = 999999; > 80 int _ = 1999966; > 81 END > 82 /* > 83 CASE(7) > 84 int N = ; > 85 int _ = ; > 86 END > 87 CASE(8) > 88 int N = ; > 89 int _ = ; > 90 END > 91 */ > 92 } > 93 // END CUT HERE
Added SRM/661-U/1B.cpp version [2687f89822088323]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static unsigned MODVAL; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 33 mint operator+(mint x, mint y) { return x+=y; } > 34 mint operator*(mint x, mint y) { return x*=y; } > 35 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 36 > 37 class ColorfulLineGraphs { public: > 38 int countWays(long long N, long long K, int M) > 39 { > 40 MODVAL = M; > 41 --K; > 42 > 43 // The problem reduces to > 44 // (K+1)(2K+1)(3K+1) ... (NK+1) > 45 // and note that > 46 // (MK+1) == 1 mod M > 47 mint v_rem = 1; > 48 for(LL n=N/M*M; n<=N; ++n) > 49 v_rem *= mint(n)*K + 1; > 50 > 51 mint v = 1; > 52 for(int n=1; n<M; ++n) > 53 v *= mint(n)*K + 1; > 54 return (v_rem * POW(v,N/M)).val; > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const int& Expected, const int& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, ColorfulLineGraphs().countWays(N, K, M));} > 72 int main(){ > 73 > 74 CASE(0) > 75 long long N = 3LL; > 76 long long K = 2LL; > 77 int M = 100000; > 78 int _ = 24; > 79 END > 80 CASE(1) > 81 long long N = 15LL; > 82 long long K = 3LL; > 83 int M = 1000000; > 84 int _ = 510625; > 85 END > 86 CASE(2) > 87 long long N = 100000LL; > 88 long long K = 100000LL; > 89 int M = 999999; > 90 int _ = 185185; > 91 END > 92 CASE(3) > 93 long long N = 1000000000000LL; > 94 long long K = 6LL; > 95 int M = 1000000; > 96 int _ = 109376; > 97 END > 98 CASE(4) > 99 long long N = 5000LL; > 100 long long K = 1000000000000LL; > 101 int M = 314159; > 102 int _ = 202996; > 103 END > 104 /* > 105 CASE(5) > 106 long long N = LL; > 107 long long K = LL; > 108 int M = ; > 109 int _ = ; > 110 END > 111 CASE(6) > 112 long long N = LL; > 113 long long K = LL; > 114 int M = ; > 115 int _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE