#988630 (C++23) No.2785 四乗足す四の末尾の０

提出ソース

結果

問題	No.2785 四乗足す四の末尾の０
ユーザー	Kiffaz17
提出日時	2024-06-14 21:58:54
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	8,145 bytes
コンパイル時間	2,670 ms
コンパイル使用メモリ	253,628 KB
実行使用メモリ	10,400 KB
最終ジャッジ日時	2024-06-14 21:59:02
合計ジャッジ時間	6,131 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	TLE	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ods;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;

using ld = long double;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
 
 
#define pii pair<int,int>
#define pll pair<ll,ll>
 
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ars(x) (x),(x+n)
 
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
 
#define For(i,a,b) for (int i=(a); i<(b); i++)
#define rep(i,a) For(i,0,a)
#define rev(i,a,b) for (int i=(a); i>(b); i--)
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define REP(i,a) FOR(i,1,a)
#define REV(i,a,b) for (int i=(a); i>=(b); i--)
 
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)(x).size())
#define mp make_pair
#define fi first
#define se second
#define FT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using vi=vector<int>;
using vll = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
 
//template <class T>
//using ods =
//   tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { __print(H); if (sizeof...(T)) cerr << ", "; dbg_out(T...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:"; dbg_out(__VA_ARGS__);

const int INF=1e9;
const ll INFI=1e15;
//----------Author: Nguyen Ho Nam,UIT, Saigon-----------------
#line 2 "Mod/mod_mul.hpp"
u64 get_nr(u64 M) {
    u64 IV = 2 - M;
    for (int i = 0; i < 5; ++i) {
        IV *= 2 - M * IV;
    }
    return IV;
}

u64 modmul(u64 x, u64 y, u64 M) {
    u64 IV=get_nr(M);
    auto t = u128(x) * y;
    u64 lo = t, hi = t >> 64;
    return (hi + M) - u64((u128(lo * IV) * M) >> 64);
}
 
u64 modpow(u64 a, u64 b, u64 M) {
    u64 res = 1;
    u64 IV = get_nr(M);
    while (b) {
        if (b & 1) {
            res = modmul(res, a, M);
        }
        a = modmul(a, a, M);
        b >>= 1;
    }
    return res;
}
//or
//only good for long long or int64_t
long long modmul2(long long a,long long b,long long mod){
   return (a*b)%mod;
}
#line 3 "NT/prime/prime_test.hpp"
bool isPrime(u64 x) {
    if (x < 64) {
        return (u64(1) << x) & 0x28208a20a08a28ac;
    }
    if (x % 2 == 0) {
        return false;
    }
    const int k = __builtin_ctzll(x - 1);
    const u64 d = (x - 1) >> k, IV = get_nr(x), R = (-x) % x, R2 = (-u128(x)) % x, nR = x - R;
    auto mr7 = [&](u64 t1, u64 t2, u64 t3, u64 t4, u64 t5, u64 t6, u64 t7) {
        u64 r1 = R, r2 = R, r3 = R, r4 = R, r5 = R, r6 = R, r7 = R;
        t1 = modmul(t1, R2, x), t2 = modmul(t2, R2, x), t3 = modmul(t3, R2, x);
        t4 = modmul(t4, R2, x), t5 = modmul(t5, R2, x), t6 = modmul(t6, R2, x), t7 = modmul(t7, R2, x);
        for (u64 b = d; b; b >>= 1) {
            if (b & 1) {
                r1 = modmul(r1, t1, x), r2 = modmul(r2, t2, x), r3 = modmul(r3, t3, x);
                r4 = modmul(r4, t4, x), r5 = modmul(r5, t5, x), r6 = modmul(r6, t6, x), r7 = modmul(r7, t7, x);
            }
            t1 = modmul(t1, t1, x), t2 = modmul(t2, t2, x), t3 = modmul(t3, t3, x);
            t4 = modmul(t4, t4, x), t5 = modmul(t5, t5, x), t6 = modmul(t6, t6, x), t7 = modmul(t7, t7, x);
        }
        r1 = min(r1, r1 - x), r2 = min(r2, r2 - x), r3 = min(r3, r3 - x);
        r4 = min(r4, r4 - x), r5 = min(r5, r5 - x), r6 = min(r6, r6 - x), r7 = min(r7, r7 - x);
        int res1 = (r1 == R) | (r1 == nR), res2 = (r2 == R) | (r2 == nR), res3 = (r3 == R) | (r3 == nR);
        int res4 = (r4 == R) | (r4 == nR), res5 = (r5 == R) | (r5 == nR), res6 = (r6 == R) | (r6 == nR), res7 = (r7 == R) | (r7 == nR);
        for (int j = 0; j < k - 1; ++j) {
            r1 = modmul(r1, r1, x), r2 = modmul(r2, r2, x), r3 = modmul(r3, r3, x);
            r4 = modmul(r4, r4, x), r5 = modmul(r5, r5, x), r6 = modmul(r6, r6, x), r7 = modmul(r7, r7, x);
            res1 |= (min(r1, r1 - x) == nR), res2 |= (min(r2, r2 - x) == nR), res3 |= (min(r3, r3 - x) == nR);
            res4 |= (min(r4, r4 - x) == nR), res5 |= (min(r5, r5 - x) == nR), res6 |= (min(r6, r6 - x) == nR), res7 |= (min(r7, r7 - x) == nR);
        }
        return res1 & res2 & res3 & res4 & res5 & res6 & res7;
    };
    if (x == 2 || x == 3 || x == 5 || x == 13 || x == 19 || x == 73 || x == 193 || x == 407521 || x == 299210837) {
        return true;
    }
    return mr7(2, 325, 9375, 28178, 450775, 9780504, 1795265022);
}
ll trail0(ll num) {
    ll cnt = 0;
    while (num % 10 == 0) {
        num /= 10;
        cnt++;
    }
    return cnt;
}

void solve()
{
  u64 tt; cin>>tt;
  vector<u64> n(tt);
  rep(i,tt){
     cin>>n[i];
  }
  rep(i,tt){
    u64 val=pow(n[i],4)+4;
    cout<<(isPrime(val)?"Yes":"No")<<'\n';
    cout<<trail0(val)<<'\n';
  }
}
int main(){
FT;
int t=1; 
//sc.read(t); int tc=0;
while(t--)
{
//tc++;
//cout << "Case #" << tc << ": ";
solve();
// cerr << "Time elapsed: " << TIME << " s.\n";
}
}

yukicoder

結果

テストケース

ソースコード