QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#132900#6740. FunctionNicolas125841WA 198ms886208kbC++171.7kb2023-08-01 03:51:022023-08-01 03:51:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-01 03:51:05]
  • 评测
  • 测评结果:WA
  • 用时:198ms
  • 内存:886208kb
  • [2023-08-01 03:51:02]
  • 提交

answer

#include <bits/extc++.h>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// To use most b i ts rather than jus t the lowest ones :
struct chash { // large odd number for C
    const uint64_t C = ll(4e18 * acos(0)) | 71;

    ll operator()(ll x) const { return __builtin_bswap64(x*C); }
};

__gnu_pbds::gp_hash_table<ll,ll,chash> rdp({},{},{},{},{1<<25});

const ll mod = 998244353;
const int N = 20210926;
const int DPC = 31625;

vector<int> lp(N+1);
vector<ll> pr;

int TN;
int LB = 0;
vector<ll> dp(DPC);

void prep(){
    for (int i=2; i <= N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; i * pr[j] <= N; ++j) {
            lp[i * pr[j]] = pr[j];
            if (pr[j] == lp[i]) {
                break;
            }
        }
    }

    while(pr[LB] < DPC)
        LB++;

    dp[1] = 1;

    for(int i = 2; i < DPC; i++){
        for(int j = 1; j * j <= i; j++){
            if(i % j)
                continue;

            dp[i] += dp[i / j];

            if(j * j != i)
                dp[i] += dp[j];

            dp[i] %= mod;
        }
    }

    for(int i = 1; i < DPC; i++)
        dp[i] = (dp[i] + dp[i - 1]) % mod;
}

ll rec(ll n){
    if(TN / n < DPC)
        return dp[TN / n];

    if(rdp.find(n) != rdp.end())
        return rdp[n];

    ll ans = 0;

    for(ll v = 2; v * n < DPC; v++)
        ans += rec(v * n);

    for(int i = LB; i < pr.size(); i++){
        if(pr[i] * n > TN)
            break;

        ans += rec(pr[i] * n);
    }

    ans %= mod;

    rdp[n] = ans;
    
    return ans;
}

int main(){
    cin >> TN;

    prep();

	cout << rec(1) << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 191ms
memory: 885272kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 198ms
memory: 885292kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 182ms
memory: 885232kb

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

score: 0
Accepted
time: 191ms
memory: 886208kb

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

score: 0
Accepted
time: 181ms
memory: 885196kb

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

score: 0
Accepted
time: 189ms
memory: 885252kb

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

score: -100
Wrong Answer
time: 179ms
memory: 885272kb

input:

100000

output:

139651864

result:

wrong answer 1st numbers differ - expected: '139804054', found: '139651864'