結果
問題 | No.129 お年玉(2) |
ユーザー |
|
提出日時 | 2015-01-16 21:47:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 881 bytes |
コンパイル時間 | 1,146 ms |
コンパイル使用メモリ | 158,836 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 22:51:00 |
合計ジャッジ時間 | 2,468 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll MOD = 1e9;int f(int n, int p){if(n < p)return 0;return (n / p) + f(n / p, p);}ll mod_pow(ll x, ll e){ll v = 1;for(;e;e>>=1){if(e & 1)v = (v * x) % MOD;x = (x * x) % MOD;}return v;}bool isp[10010];int main(){ll N, M;cin >> N >> M;N /= 1000;N %= M;for(int i=2;i<=M;i++)isp[i] = true;for(int p=2;p*p<=M;p++){if(!isp[p])continue;for(int kp=p*p;kp<=M;kp+=p)isp[kp] = false;}ll res = 1;for(int p=2;p<=M;p++){if(!isp[p])continue;int e = f(M, p) - f(N, p) - f(M - N, p);res = (res * mod_pow(p, e)) % MOD;}cout << res << endl;return 0;}