結果
問題 |
No.1747 Many Formulae 2
|
ユーザー |
![]() |
提出日時 | 2021-11-19 21:40:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,896 bytes |
コンパイル時間 | 3,690 ms |
コンパイル使用メモリ | 250,336 KB |
最終ジャッジ日時 | 2025-01-25 20:08:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; #define rep(i, n) for(ll i = 0; i < n; i++) #define rep2(i, m, n) for(ll i = m; i <= n; i++) #define rrep(i, m, n) for(ll i = m; i >= n; i--) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define MAX(x) *max_element(all(x)) #define MIN(x) *min_element(all(x)) #define SZ(a) ((ll)(a).size()) using namespace std; typedef long long ll; typedef pair<int, int> P; const int dx[4] = { -1, 1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; const int inf = 1e9 + 1; const ll INF = 1e18; const double pi = acos(-1); using Graph = vector<vector<ll>>; using REV_PQ = priority_queue<int, vector<int>, greater<int>>; using PQ = priority_queue<int>; //typedef atcoder::modint998244353 mint; //typedef atcoder::modint1000000007 mint; struct Edge { ll u, v, cost; }; bool comp(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; int n = SZ(s); int res = 0; if (n == 1) { ll cur = (ll)(s[0] - '0'); for (ll j = 2; j * j <= cur; j++) { if (cur % j == 0) { cout << 0 << endl; return 0; } } if (cur == 1) cout << 0 << endl; else cout << 1 << endl; return 0; } rep(i, 1 << (n - 1)) { ll sum = 0; ll cur = (ll)(s[0] - '0'); rep(j, n - 1) { if ((i >> j) & 1) { sum += cur; cur = (ll)(s[j + 1] - '0'); } else { cur = cur * 10 + (ll)(s[j + 1] - '0'); } } sum += cur; bool ok = true; for (ll j = 2; j * j <= sum; j++) { if (sum % j == 0) ok = false; } if (ok) res++; } cout << res << endl; }