結果
問題 | 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; }