結果

問題 No.1747 Many Formulae 2
コンテスト
ユーザー Gautam Verma
提出日時 2021-11-19 21:56:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,562 bytes
コンパイル時間 1,709 ms
コンパイル使用メモリ 193,384 KB
最終ジャッジ日時 2025-01-25 20:19:38
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
#define all(x) x.begin(), x.end()
using u64 = uint64_t;
using u128 = __uint128_t;
u64 binpower(u64 base, u64 e, u64 mod) {
   u64 result = 1;
   base %= mod;
   while (e) {
      if (e & 1)
         result = (u128)result * base % mod;
      base = (u128)base * base % mod;
      e >>= 1;
   }
   return result;
}
bool check_composite(u64 n, u64 a, u64 d, int s) {
   u64 x = binpower(a, d, n);
   if (x == 1 || x == n - 1)
      return false;
   for (int r = 1; r < s; r++) {
      x = (u128)x * x % n;
      if (x == n - 1)
         return false;
   }
   return true;
};
bool MillerRabin(u64 n) {
   if (n < 2)
      return false;
   int r = 0;
   u64 d = n - 1;
   while ((d & 1) == 0) {
      d >>= 1;
      r++;
   }
   for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      if (n == a)
         return true;
      if (check_composite(n, a, d, r))
         return false;
   }
   return true;
}
void solve() {
   string s;
   cin >> s;
   int n = s.length(), ans = 0;
   for (int i = 0, en = 1 << (n - 1); i < en; i++) {
      ll p = 0;
      string t = string(1, s[0]);
      for (int j = 0; j < n - 1; j++) {
         if ((i >> j) & 1) {
            t += s[j + 1];
         } else {
            p += stoll(t), t = s[j + 1];
         }
      }
      p += stoll(t);
      if (MillerRabin(p))
         ans++;
   }
   cout << ans << '\n';
}
int main() {
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);
   solve();
   return 0;
}
0