結果
問題 | No.2207 pCr検査 |
ユーザー |
|
提出日時 | 2024-10-06 22:45:28 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,513 bytes |
コンパイル時間 | 1,127 ms |
コンパイル使用メモリ | 118,940 KB |
実行使用メモリ | 91,776 KB |
最終ジャッジ日時 | 2024-10-06 22:46:19 |
合計ジャッジ時間 | 45,702 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | RE * 30 |
ソースコード
#include<iostream>#include<string>#include<queue>#include<vector>#include<cassert>#include<random>#include<set>#include<map>#include<cassert>#include<unordered_map>#include<bitset>#include<numeric>#include<algorithm>using namespace std;typedef long long ll;const int inf=1<<30;const ll INF=1LL<<62;typedef pair<int,ll> P;typedef pair<int,P> PP;const ll MOD=998244353;int main(){int k;cin>>k;vector<ll> p(k),e(k);for(int i=0;i<k;i++){cin>>p[i]>>e[i];}ll cp=p.back();vector<ll> mpf(cp+1);for(int i=2;i<=cp;i++){if(mpf[i]==0){for(int j=i;j<=cp;j+=i){mpf[j]=i;//jはiで割れる}}}ll dif=k;for(ll r=1;r<=cp/2;r++){for(ll tmp=cp-r+1;tmp!=1;tmp/=mpf[tmp]){// cp C tmp を試す. tmp=cp-r+1,cp-r+2,...,cp//tmpを素因数分解するif(e[mpf[tmp]]==0){dif++;}e[mpf[tmp]]--;if(e[mpf[tmp]]!=0){dif--;}}for(ll tmp=r;tmp!=1;tmp/=mpf[tmp]){//cp C tmpを試す. tmp=1,2,3,...,rif(e[mpf[tmp]]==0){dif++;}e[mpf[tmp]]++;if(e[mpf[tmp]]!=0){dif--;}if(dif==0){cout<<cp<<' '<<r<<endl;return 0;}}}cout<<-1<<' '<<-1<<endl;}