結果
問題 | No.1747 Many Formulae 2 |
ユーザー |
|
提出日時 | 2022-05-05 17:23:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 875 bytes |
コンパイル時間 | 766 ms |
コンパイル使用メモリ | 82,004 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 18:52:19 |
合計ジャッジ時間 | 1,618 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<ctime> #include<string> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; typedef long long LL; const int MR=1e6+10; bool isp(LL x){ if(x<2) return false; for(LL i=2;i*i<=x;i++){ if(x%i==0) return false; } return true; } int n,a[15],cnt; LL num[15][15]; //上次在s[last]的后面添加了加号 void dfs(int last,LL sum){ if(isp(sum+num[last+1][n])){ cnt++; } for(int i=last+1;i<n;i++){ dfs(i,sum+num[last+1][i]); } } string s; int main(){ cin>>s; n=s.size(); for(int i=1;i<=n;i++) a[i]=s[i-1]-'0'; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ num[i][j]=num[i][j-1]*10+a[j]; } } dfs(0,0); printf("%d\n",cnt); return 0; }