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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 49 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 69 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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