結果
問題 | No.1747 Many Formulae 2 |
ユーザー |
|
提出日時 | 2021-11-19 22:17:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,295 bytes |
コンパイル時間 | 1,936 ms |
コンパイル使用メモリ | 199,608 KB |
最終ジャッジ日時 | 2025-01-25 20:28:03 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e17;const ll dy[9]={0,1,-1,0,1,1,-1,-1,0};const ll dx[9]={1,0,0,-1,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}//N=10^5,s<=10^10で1000msくらいstruct fast_factorize{using i128=__int128_t;vector<int> wit={2, 325, 9375, 28178, 450775, 9780504, 1795265022};ll modpow(ll a,ll b,ll m){ll ret=1,now=a;while(b){if(b&1)ret=i128(ret)*now%m;now=i128(now)*now%m;b>>=1;}return ret;}bool isprime(ll p){if(p==2)return true;if(p==1||p%2==0)return false;ll s=0,d=p-1;while(d%2==0){d/=2;s++;}for(auto a:wit){if(a%p==0)continue;bool iscomp=true;ll x=modpow(a,d,p);if(x==1)iscomp=false;rep(i,s){if(x==p-1)iscomp=false;x=i128(x)*x%p;}if(iscomp)return false;}return true;}long long find_factor(long long n) {assert(n > 1);if (n % 2 == 0) return 2;if (isprime(n)) return n;auto f = [&](__int128 x) -> long long { return (x * x + 1) % n; };for (int t = 1;; t++) {long long x0 = t, m = max(n >> 3, 1LL), x, ys, y = x0, r = 1, g, q = 1;do {x = y;for (int i = r; i--;) y = f(y);long long k = 0;do {ys = y;for (int i = min(m, r - k); i--;) y = f(y), q = __int128(q) * abs(x - y) % n;g = gcd(q, n);k += m;} while (k < r and g <= 1);r <<= 1;} while (g <= 1);if (g == n) {do {ys = f(ys);g = gcd(abs(x - ys), n);} while (g <= 1);}if (g != n) return g;}}vector<ll> factor(ll n){vector<ll> ret;while(n>1){ll f=find_factor(n);if(f<n){auto tmp=factor(f);ret.insert(ret.end(),all(tmp));}else ret.emplace_back(n);n/=f;}sort(all(ret));return ret;}};int main(){string s;cin >> s;ll n=s.size();fast_factorize fz;ll ans=0;repl(bit,1<<(n-1),1<<(n)){ll ret=0,now=0;rep(i,n){now*=10;now+=(s[i]-'0');if(bit>>i&1){ret+=now;now=0;}}//cout << ret << endl;ans+=fz.isprime(ret);}cout << ans << endl;}