結果
問題 | No.1747 Many Formulae 2 |
ユーザー |
![]() |
提出日時 | 2021-11-19 21:46:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 3,312 bytes |
コンパイル時間 | 2,094 ms |
コンパイル使用メモリ | 177,724 KB |
実行使用メモリ | 12,112 KB |
最終ジャッジ日時 | 2024-12-31 22:42:19 |
合計ジャッジ時間 | 3,043 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using V = vector<ll>;using VV = vector<V>;using VVV = vector<VV>;using VVVV = vector<VVV>;using VVVVV = vector<VVVV>;using VVVVVV = vector<VVVVV>;using VS = vector<string>;using VB = vector<bool>;using VVB = vector<VB>;using P = pair<ll,ll>;using M = map<ll,ll>;using Q = queue<ll>;using PQ = priority_queue<ll>;using PQG = priority_queue<ll,V,greater<ll>>;using S = set<ll>;using VP = vector<P>;const ll MOD = 1000000007;const ll mod = 998244353;const ll INF = 1LL << 60;#define rep(i,n) for(ll i = 0; i < n; i++)#define rep2(i,s,n) for(ll i = s; i < n; i++)#define per(i,n) for(ll i = n-1; i >= 0; i--)#define per2(i,s,n) for(ll i = n-1; i >= s; i--)#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define fi first#define se second#define pb push_back#define pf push_front#define ppb pop_back#define ppf pop_front#define eb emplace_back#define lb lower_bound#define ub upper_boundtemplate<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}template<class T>void Vin(vector<T>&a){rep(i,(int)a.size())cin>>a[i];}template<class T>void VVin(vector<vector<T>>&a){rep(i,(ll)a.size())Vin(a[i]);}template<class T>void Vout(const vector<T>&a){rep(i,(int)a.size())cout<<a[i]<<endl;}ll power(ll a,ll b,const ll&M){a%=M;ll res=1;while(b>0){if(b&1)res=res*a%M;a=a*a%M;b>>=1;}return res;}const ll H[4] = {0,1,0,-1}, W[4] = {1,0,-1,0};struct Sieve {long long n;vector<long long> f, primes;Sieve(long long n): n(n), f(n+1) {f[0] = f[1] = -1;for(long long i = 2; i <= n; i++) {if(f[i]) continue;primes.push_back(i);f[i] = i;for(long long j = i*i; j <= n; j += i) if(!f[j]) f[j] = i;}}bool isPrime(long long x) {return f[x] == x;}vector<long long> factorList(long long x) {if(!x) return {};vector<long long> res;while(x != 1) {res.push_back(f[x]);x /= f[x];}return res;}vector<pair<long long,long long>> factor(long long x) {vector<long long> fl = factorList(x);if(fl.size() == 0) return {};vector<pair<long long,long long>> res = {{fl[0],0}};for(long long p : fl) {if(p == res.back().fi) res.back().se++;else res.emplace_back(p,1);}return res;}vector<pair<long long,long long>> bigfactor(long long x) {if(!x) return {};vector<pair<long long,long long>> res;for(long long p : primes) {long long y = 0;while(x%p == 0) x /= p, y++;if(y) res.emplace_back(p,y);}if(x != 1) res.emplace_back(x,1);return res;}} p(1e6);int main() {string s;cin >> s;ll ans = 0;auto dfs = [&](auto f, ll a, string s) -> void {ll ss = s.size();rep(i,ss-1) f(f,a+stoll(s.substr(0,i+1)),s.substr(i+1,ss-i-1));a += stoll(s);if(a <= 1e6) {if(p.isPrime(a)) ans++;}else if((ll)p.bigfactor(a).size() == 1) ans++;};dfs(dfs,0,s);cout << ans << endl;}