結果
問題 | No.129 お年玉(2) |
ユーザー |
👑 |
提出日時 | 2020-03-15 19:47:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 122 ms / 5,000 ms |
コード長 | 1,081 bytes |
コンパイル時間 | 739 ms |
コンパイル使用メモリ | 73,384 KB |
実行使用メモリ | 11,184 KB |
最終ジャッジ日時 | 2024-11-25 08:59:36 |
合計ジャッジ時間 | 8,168 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <iostream> #include <vector> using namespace std; struct SieveEratos{ vector<bool> t; SieveEratos(int n):t(n+1,true){ t[0] = t[1] = false; for(int i = 2; n >= i; i++){ if(t[i]){ for(int j = i+i; n >= j; j+=i){ t[j] = false; } } } } bool operator[](int x){return t[x];} }; const int mod = 1000000000; long long C(int n,int r,vector<int> P){ //nCr = nC(n-r) if(r > n/2)r = n-r; int a[n];for(int i = 0; r > i; i++)a[i] = n-i; for(int p:P){ //素数p > rだったらforに入らないので if(p > r)break; for(int q = p; r >= q; q *= p){ int m = n%q; for(int i = m, j = 0; r/q > j;i+=q,j++){ //cout << i << " " << p << endl; a[i]/=p; } } } long mul = 1; for(int i = 0; r > i; i++){ //cout << a[i] << " "; mul = (mul*a[i])%mod; } //cout << endl; return mul; } int main(){ vector<int> P; SieveEratos A(10000000); for(int i = 0; 10000000 > i; i++){ if(A[i])P.push_back(i); } long long n,m;cin>>n>>m; n = n/1000; int N = m; int R = n%m; cout << C(N,R,P) << endl; }