結果
問題 | No.1747 Many Formulae 2 |
ユーザー |
|
提出日時 | 2021-11-19 22:14:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,153 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 194,992 KB |
最終ジャッジ日時 | 2025-01-25 20:27:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include<bits/stdc++.h>typedef uint64_t u64;typedef int64_t i64;using namespace std;void solve();int main(){cout<<fixed<<setprecision(15);bool is_multicase=false;int T=1;if(is_multicase){cin>>T;}for(int i=0;i<T;++i){solve();}return 0;}template<typename T> void turtle_in(T& n){cin>>n;}template<typename T,typename U> void turtle_in(pair<T,U>& p){turtle_in(p.first);turtle_in(p.second);}template<typename T> void turtle_in(vector<T>& v){for(auto& u:v){turtle_in(u);}}template<typename T> void turtle_out(T& n){cout<<n;}template<typename T,typename U> void turtle_out(pair<T,U>& p){cout<<"{";turtle_out(p.first);cout<<", ";turtle_out(p.second);cout<<"}";}template<typename T> void turtle_out(vector<T>& v){for(int i=0;i<int(v.size());++i){turtle_out(v[i]);if(i!=v.size()-1){cout<<" ";}}cout<<endl;}template<typename T> void turtle_out(vector<vector<T>>& v){for(int i=0;i<int(v.size());++i){turtle_out(v[i]);}}void scan(){}template<typename T,class... Args> void scan(T& n,Args&... args){turtle_in(n);scan(args...);}void print(){}template<typename T,class... Args> void print(T n,Args... args){turtle_out(n);print(args...);}template<typename T> void println(T n){turtle_out(n);cout<<endl;}template<typename T,class... Args> void println(T n,Args... args){turtle_out(n);cout<<" ";println(args...);}template<u64 mod> struct modint{u64 val;modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){}modint operator-(){return modint(mod-val);}modint operator+(modint rhs){return modint(*this)+=rhs;}modint operator-(modint rhs){return modint(*this)-=rhs;}modint operator*(modint rhs){return modint(*this)*=rhs;}modint operator/(modint rhs){return modint(*this)/=rhs;}modint &operator+=(modint rhs){val+=rhs.val;val-=((val>=mod)?mod:0);return (*this);}modint &operator-=(modint rhs){val+=((val<rhs.val)?mod:0);val-=rhs.val;return (*this);}modint &operator*=(modint rhs){val=val*rhs.val%mod;return (*this);}modint &operator/=(modint rhs){u64 ex=mod-2;modint now=1;while(ex){now*=((ex&1)?rhs:1);rhs*=rhs,ex>>=1;}return (*this)*=now;}bool operator==(modint rhs){return val==rhs.val;}bool operator!=(modint rhs){return val!=rhs.val;}friend std::ostream &operator<<(std::ostream& os,modint x){return os<<(x.val);}friend std::istream &operator>>(std::istream& is,modint& x){u64 t;is>>t,x=t;return is;}};template<typename T,typename U> T power(T a,U n){T res=1;while(n>0){if(n%2==1){res*=a;}a*=a;n/=2;}return res;}template<typename T> struct genrand{uniform_int_distribution<T> gen;mt19937 engine;genrand(T a,T b):gen(a,b){random_device seed_gen;engine.seed(seed_gen());}T operator()(){return gen(engine);}};template<typename T> struct comb{vector<T> dat,idat;comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){for(int i=1;i<=mx;++i){dat[i]=dat[i-1]*i;}idat[mx]/=dat[mx];for(int i=mx;i>0;--i){idat[i-1]=idat[i]*i;}}T operator()(int n,int k){if(n<0||k<0||n<k){return 0;}return dat[n]*idat[k]*idat[n-k];}};template<typename T> struct matrix{vector<vector<T>> val;int height,width;matrix(int H,int W,T init=0):val(H,vector<T> (W,init)),height(H),width(W){}vector<T> &operator[](int i){return val[i];}matrix operator+(matrix rhs){return matrix(*this)+=rhs;}matrix operator*(matrix rhs){return matrix(*this)*=rhs;}matrix operator+=(matrix rhs){for(int i=0;i<rhs.height;++i){for(int j=0;j<rhs.width;++j){(*this)[i][j]+=rhs[i][j];}}return (*this);}matrix operator*=(matrix rhs){matrix<T> res(height,rhs.width,0);for(int i=0;i<this->height;++i){for(int j=0;j<rhs.width;++j){for(int k=0;k<this->width;++k){res[i][j]+=(*this)[i][k]*rhs[k][j];}}}return (*this)=res;}matrix identity(int n){matrix res(n,n);for(int i=0;i<n;++i){res[i][i]=1;}return res;}matrix mat_pow(i64 k){int n=(*this).height;matrix res=identity(n),now=(*this);while(k>0){if(k%2==1){res*=now;}now*=now;k/=2;}return (*this)=res;}};bool is_prime(i64 n){if(n==1){return 0;}for(i64 i=2;i*i<=n;++i){if(n%i==0){return 0;}}return 1;}void solve(){constexpr u64 mod=998244353;typedef modint<mod> mint;string S;scan(S);int N=S.size();i64 ans=0;for(int i=0;i<(1<<(N-1));++i){bitset<10> bit(i);i64 sum=0,now=S[0]-'0';for(int j=0;j<N-1;++j){if(bit[j]){sum+=now;now=S[j+1]-'0';}else{now=now*10+(S[j+1]-'0');}}sum+=now;ans+=is_prime(sum);}println(ans);}