QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744224#9619. 乘积,欧拉函数,求和BaseAI#WA 8ms5612kbC++232.4kb2024-11-13 21:13:232024-11-13 21:13:26

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 21:13:26]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:5612kb
  • [2024-11-13 21:13:23]
  • 提交

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'