結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2022-10-25 00:05:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 202 ms / 2,000 ms |
コード長 | 2,104 bytes |
コンパイル時間 | 2,865 ms |
コンパイル使用メモリ | 246,536 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-03 02:35:49 |
合計ジャッジ時間 | 5,332 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function 'll pho(ll)': main.cpp:56:23: warning: 'w' is used uninitialized [-Wuninitialized] 56 | while (!w || w==2) w=rand()%(x-1)+1; | ~^~~ main.cpp:55:33: note: 'w' was declared here 55 | ll u=rand()%(x-1)+1,v=u,w,t=1; int i=2,k=2; | ^
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;template<class t> using vc = vector<t>;template<class t> using vvc = vc<vc<t>>;using pi = pair<int,int>;using pl = pair<ll,ll>;using vi = vc<int>;using vvi = vvc<int>;using vl = vc<ll>;using vvl = vvc<ll>;#define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++)#define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--)#define all(a) a.begin(),a.end()#define print(n) cout << n << '\n'#define pritn(n) print(n)#define printv(n,a) {copy(all(n),ostream_iterator<a>(cout," ")); cout<<"\n";}#define printvv(n,a) {for(auto itr:n) printv(itr,a);}#define rup(a,b) (a+b-1)/b#define input(A,N) rep(i,0,N) cin>>A[i]#define chmax(a,b) a = max(a,b)#define chmin(a,b) a = min(a,b)ll gcd(ll n, ll m){if (m > n) swap(n,m);if (m == 0) return n;return gcd(m,n%m);}ll ksc(ll x,ll y,ll p){ll t=0; for (; y; y>>=1,x=(x<<1)%p) if (y&1) t=(t+x)%p;return t;}ll ksm(ll x,ll y,ll p){ll t=1; for (; y; y>>=1,x=ksc(x,x,p)) if (y&1) t=ksc(t,x,p);return t;}bool isprm(ll x){if (x==2) return 1; if (x==1 || !(x&1)) return 0;ll t=x-1; int len=0,i,j;for (; !(t&1); t>>=1) len++;for (i=1; i<=10; i++){ll k=ksm(rand()%(x-1)+1,t,x);for (j=1; j<=len; j++,k=ksc(k,k,x))if (j<len-1 && ksc(k,k,x)==1 && k!=1 && k!=x-1) return 0;if (k!=1) return 0;}return 1;}ll pho(ll x){ll u=rand()%(x-1)+1,v=u,w,t=1; int i=2,k=2;while (!w || w==2) w=rand()%(x-1)+1;for (; t==1; i++){if (i==k){ v=u; k<<=1; }u=(ksc(u,u,x)+x-w)%x;t=gcd(v-u+x,x);}return t;}int main(){cout << fixed << setprecision(15);int n;cin>>n;vi dp(n+1,0);for(int i = 2;i<=n;i++){if(!isprm(i)) continue;for(int j = n;j>=0;j--){int ni = j - i;if(ni<0) continue;if(dp[ni]==0) continue;chmax(dp[j],dp[ni]+1);}chmax(dp[i],1);}if(dp[n]==0) print(-1);else print(dp[n]);//printv(dp,int);//system("pause");return 0;}