QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744224 | #9619. 乘积,欧拉函数,求和 | BaseAI# | WA | 8ms | 5612kb | C++23 | 2.4kb | 2024-11-13 21:13:23 | 2024-11-13 21:13:26 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3007;
const int mod = 998244353;
int n;
vector<int> P;
bool visP[N];
void InitPrime() {
visP[1] = 1;
for(int i=2;i<N;++i) {
if(!visP[i]) P.push_back(i);
for(auto p : P) {
if(p*i >= N) break;
visP[p * i] = 1;
if(i%p == 0) break;
}
}
}
typedef pair<int,int> pii;
#define mp make_pair
vector<pii> vec[N];
int MaxFac(int x,int &s) {
for(int i=0;i<16;++i) {
auto p = P[i];
if(x%p == 0) s |= (1ll << i);
while(x%p == 0) x /= p;
}
return x;
}
const int M = 16;
const int S = (1<<M);
int f[2][S][2];
void add(int &x,int y) {
x = (x + y) % mod;
}
void mul(int &x,int y) {
x = (long long)x * y % mod;
}
void solve() {
cin >> n;
vector<int> a(n);
for(int i=0;i<n;++i) cin >> a[i];
set<int> st;
for(auto x : a) {
int s = 0;
int fac = MaxFac(x, s);
vec[fac].push_back(mp(x, s));
st.insert(fac);
}
int now = 1, last = 0;
f[last][0][1] = 1;
for(auto y : st) {
for(int s=0;s<S;++s) {
add(f[last][s][0], f[last][s][1]);
f[last][s][1] = 0;
}
//cout << "test:: " << f[last][0][0] << "\n";
for(auto [x, xs] : vec[y]) {
for(int s=0;s<S;++s) {
f[now][s][0] = f[last][s][0];
f[now][s][1] = f[last][s][1];
}
for(int s=0;s<S;++s) {
int fir = xs & (xs^s);
int sec = xs & (s);
int val = 1;
for(int j=0;j<16;++j) {
if(fir & (1ll<<j)) mul(val, P[j]-1);
if(sec & (1ll<<j)) mul(val, P[j]);
//if((fir & (1ll<<j) )==(sec & (1ll<<j)) && ((fir & (1ll<<j)) == 1)) cout << "wa" << "\n";
}
add(f[now][s|xs][1], f[last][s][0]*val%mod*(max(1ll, y-1))%mod);
add(f[now][s|xs][1], f[last][s][1]*val%mod*(y)%mod);
}
now ^= 1, last ^= 1;
}
}
int ans = 0;
for(int s=0;s<S;++s) {
//cout << f[last][s][0] << " " << f[last][s][1] << "\n";
add(ans, f[last][s][0]+f[last][s][1]);
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
InitPrime();
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 5612kb
input:
5 1 6 8 6 2
output:
298
result:
wrong answer 1st lines differ - expected: '892', found: '298'