QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#574095#9309. GraphAndyqian7TL 1604ms846760kbC++141.9kb2024-09-18 20:47:172024-09-18 20:47:17

Judging History

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

  • [2024-09-18 20:47:17]
  • 评测
  • 测评结果:TL
  • 用时:1604ms
  • 内存:846760kb
  • [2024-09-18 20:47:17]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int len, lim, lenp, a[7000000], g[7000000];
const int MOD = 998244353;
const int N = 1e8 + 3;
bitset<N> v;
int p[N >> 2], sum[N];
map<int, int> mp;
void seive()
{
    int cnt = 0;
    for (int i = 2; i < N; i++)
    {
        if (!v[i])
            p[cnt++] = i;
        for (int j = 0; j < cnt && i * p[j] < N; j++)
        {
            v[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}
int fp(int x, int k)
{
    if (!k)
        return 1;
    if (k & 1)
        return x * fp(x, k - 1) % MOD;
    int tmp = fp(x, k >> 1);
    return tmp * tmp % MOD;
}
inline int get_index(int n, int x)
{
    if (x <= lim)
        return x;
    else
        return len - n / x + 1;
}
int cnt(int n)
{
    if (n < N)
        return sum[n];
    if (mp.count(n))
        return mp[n];
    lim = sqrt(n);
    len = lenp = 0;
    for (int i = 1; i <= n; i = a[len] + 1)
    {
        a[++len] = n / (n / i);
        g[len] = a[len] - 1;
    }
    for (int i = 2; i <= lim; ++i)
    {
        if (g[i] != g[i - 1])
        {
            ++lenp;
            for (int j = len; a[j] >= 1ll * i * i; --j)
                g[j] = g[j] - g[get_index(n, a[j] / i)] + lenp - 1;
        }
    }
    mp[n] = g[len];
    return g[len];
}
int f(int n)
{
    return cnt(n) - cnt(n / 2);
}
int F(int n)
{
    if (n <= 2)
        return 1;
    if (n == 3)
        return 3;
    int tmp = f(n);
    return fp(n % MOD, tmp) * (n % MOD - tmp % MOD - 1 + MOD) % MOD;
}
signed main()
{
    seive();
    for (int i = 2; i < N; i++)
        sum[i] = sum[i - 1] + !v[i];
    int n;
    cin >> n;
    int ans = 1;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        ans = ans * fp(F(n / l), r - l + 1) % MOD;
    }
    cout << ans;
}

詳細信息

Test #1:

score: 100
Accepted
time: 509ms
memory: 844484kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 492ms
memory: 843876kb

input:

2

output:

1

result:

ok answer is '1'

Test #3:

score: 0
Accepted
time: 474ms
memory: 843976kb

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

score: 0
Accepted
time: 491ms
memory: 843496kb

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

score: 0
Accepted
time: 459ms
memory: 843148kb

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

score: 0
Accepted
time: 460ms
memory: 844420kb

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

score: 0
Accepted
time: 471ms
memory: 843176kb

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

score: 0
Accepted
time: 464ms
memory: 843800kb

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

score: 0
Accepted
time: 468ms
memory: 843344kb

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 497ms
memory: 843788kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

score: 0
Accepted
time: 454ms
memory: 844744kb

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 516ms
memory: 844328kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 497ms
memory: 844428kb

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 567ms
memory: 845700kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 709ms
memory: 845712kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: 0
Accepted
time: 1604ms
memory: 846760kb

input:

19834593299

output:

523663743

result:

ok answer is '523663743'

Test #17:

score: -100
Time Limit Exceeded

input:

52500109238

output:


result: