結果

問題 No.458 異なる素数の和
ユーザー momoyuumomoyuu
提出日時 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;
      |                                 ^

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0