QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#574575 | #3799. It's Surely Complex | BongoCatEnjoyer# | WA | 0ms | 3676kb | C++20 | 2.6kb | 2024-09-18 22:57:40 | 2024-09-18 22:57:41 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define all(v) (v).begin(), (v).end()
#define forn(var, n) for (ll (var) = 0; (var) < (n); ++(var))
#define forr(var, start, end) for (ll (var) = (start); (var) < (end); ++(var))
#define fori(var, start, end) for (ll (var) = (start); (var) > (end); --(var))
#define fora(var, obj) for (auto (var) : (obj))
#define MOD1 (ll) (1e9 + 7)
#define MOD9 (ll) (998244353)
#define prints(x) cout << (x) << " "
#define println(x) cout << (x) << "\n"
#define newl() cout << "\n"
using namespace std;
ll mod(ll a, ll m) {
return (a % m + m) % m;
}
ll powmod(ll a, ll b, ll m) {
ll res = 1;
while (b) {
if (b & 1) res = mod(res * a, m);
a = mod(a * a, m);
b >>= 1;
}
return mod(res, m);
}
void solve() {
ll p, n; cin >> p >> n;
vector<ll> a(p, mod(n / p, p));
forn(i, mod(n, p) + 1) a[i] = mod(a[i] + 1, p);
// forn(i, min(10LL, p)) prints(a[i]); newl();
vector<ll> b(p);
forn(i, p - 1) {
forr(j, i + 1, p) {
ll is = mod(mod(i % p, p) * mod(i % p, p), p);
ll js = mod(mod(j % p, p) * mod(j % p, p), p);
b[(is + js) % p] = (b[(is + js) % p] % p + ((a[i] % p) * (a[j] % p)) % p) % p;
}
}
// forn(i, min(10LL, p)) prints(b[i]); newl();
ll magic1 = 1, cnt = 0;
forn(i, p) {
magic1 = (magic1 * powmod(i, b[i], p)) % p;
cnt += 2 * b[i];
}
// prints(magic1); println(cnt);
ll magic2 = 1, cnt2 = 0;
forr(i, 1, p) {
magic2 = mod(magic2 * powmod(i, a[i], p), p);
cnt2 += a[i];
}
magic1 = mod(mod(magic1 * magic2, p) * powmod(2, cnt2 / 2, p), p);
cnt += cnt2;
// prints(magic1); println(cnt);
if (cnt == 0) magic1 = 0;
ll c = cnt % 8;
pair<ll, ll> ans = {0, 0};
if (c >= 1 && c <= 3) {
ans.second = mod(magic1, p);
} else if (c >= 5 && c <= 7) {
ans.second = mod(-magic1, p);
} else {
ans.second = 0;
}
if (c <= 1 || c >= 7) {
ans.first = mod(magic1, p);
} else if (c >= 3 && c <= 5) {
ans.first = mod(-magic1, p);
} else {
ans.first = 0;
}
prints(ans.first); println(ans.second);
return;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 1
output:
1 1
result:
ok single line: '1 1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 2
output:
1 1
result:
ok single line: '1 1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 3
output:
0 0
result:
ok single line: '0 0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 4
output:
0 0
result:
ok single line: '0 0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
3 1
output:
2 1
result:
ok single line: '2 1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 2
output:
2 0
result:
ok single line: '2 0'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3576kb
input:
3 3
output:
0 1
result:
wrong answer 1st lines differ - expected: '1 0', found: '0 1'