結果

問題 No.458 異なる素数の和
ユーザー momoyuumomoyuu
提出日時 2022-10-25 00:05:29
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 84 ms
5,376 KB
testcase_02 AC 96 ms
5,376 KB
testcase_03 AC 29 ms
5,376 KB
testcase_04 AC 35 ms
5,376 KB
testcase_05 AC 178 ms
5,376 KB
testcase_06 AC 96 ms
5,376 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 176 ms
5,376 KB
testcase_09 AC 16 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 202 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 20 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 91 ms
5,376 KB
testcase_28 AC 196 ms
5,376 KB
testcase_29 AC 10 ms
5,376 KB
testcase_30 AC 67 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0