QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497238 | #8508. DiviDuelo | Liuhao | WA | 3ms | 3744kb | C++23 | 2.7kb | 2024-07-28 21:36:33 | 2024-07-28 21:36:33 |
Judging History
answer
//
// Created by liuhao on 2024/7/28.
//
// /## /## /## /###### /## /##
// | ## |__/ | ## /##__ ## | ## | ##
// | ## /## /## /## | ####### /###### /###### |__/ \ ## | ## | ##
// | ## | ## | ## | ## | ##__ ## |____ ## /##__ ## /######/ | ########
// | ## | ## | ## | ## | ## \ ## /####### | ## \ ## /##____/ |_____ ##
// | ## | ## | ## | ## | ## | ## /##__ ## | ## | ## | ## | ##
// | ## | ## | ######/ | ## | ## | ####### | ######/ | ######## | ##
// |__/ |__/ \______/ |__/ |__/ \_______/ \______/ |________/ |__/
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define endl '\n'
#define vii vector<vector<int>>
using ll = long long;
using f64 = long double;
ll p;
f64 invp;
void setmod(ll x) {
p = x, invp = (f64) 1 / x;
}
ll mul(ll a, ll b) {
ll z = a * invp * b + 0.5;
ll res = a * b - z * p;
return res + (res >> 63 & p);
}
ll pow(ll a, ll x, ll res = 1) {
for (; x; x >>= 1, a = mul(a, a))
if (x & 1) res = mul(res, a);
return res;
}
bool checkprime(ll p) {
if (p == 1) return 0;
setmod(p);
ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
for (ll a: {2, 3, 5, 7, 11, 13, 82, 373}) {
if (a % p == 0) continue;
ll x = pow(a, s), y;
for (int i = 0; i < d; ++i, x = y) {
y = mul(x, x);
if (y == 1 && x != 1 && x != p - 1) return 0;
}
if (x != 1) return 0;
}
return 1;
}
ll rho(ll n) {
if (!(n & 1)) return 2;
static std::mt19937_64 gen((size_t) "hehezhou");
ll x = 0, y = 0, prod = 1;
auto f = [&](ll o) { return mul(o, o) + 1; };
setmod(n);
for (int t = 30, z = 0; t % 64 || std::gcd(prod, n) == 1; ++t) {
if (x == y) x = ++z, y = f(x);
if (ll q = mul(prod, x + n - y)) prod = q;
x = f(x), y = f(f(y));
}
return std::gcd(prod, n);
}
std::vector<ll> factor(ll x) {
std::vector<ll> res;
auto f = [&](auto f, ll x) {
if (x == 1) return;
if (checkprime(x)) return res.push_back(x);
ll y = rho(x);
f(f, y), f(f, x / y);
};
f(f, x), sort(res.begin(), res.end());
return res;
}
signed main() {
#ifdef Liuhao
freopen("in.txt", "r", stdin);
#else
ios;
#endif
int n;
cin >> n;
vector<int>div;
for(int i=1;i*i<=n;i++){
if(n%i==0){
div.push_back(i);
if(n/i!=i)div.push_back(n/i);
}
}
std::sort(div.begin(), div.end());
int d=n;
for(int i=1;i<div.size();i++){
d=gcd(d,div[i]);
}
if(div.size()==2||div.size()==4||d!=1&&d%2==0)cout<<"Y"<<endl;
else cout<<"N"<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
10
output:
Y
result:
ok "Y"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
9
output:
N
result:
ok "N"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1
output:
N
result:
ok "N"
Test #4:
score: 0
Accepted
time: 3ms
memory: 3612kb
input:
549755813888
output:
Y
result:
ok "Y"
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3532kb
input:
274877906944
output:
Y
result:
wrong answer 1st words differ - expected: 'N', found: 'Y'