#1711. 时间复杂度

时间复杂度

题目描述

一年半前,在 nantf 是个连线性筛和 O(n)O(\sqrt{n}) 判断素数都不会的蒟蒻时,他遇到了这样一道题:

给定正整数 nn,求在 11nn 之间有多少个质数。
1n10111\le n\le 10^{11}

nantf 当然知道暴力会超时,但是他也没有办法。

突然,他想到了:判断素数的复杂度是跑不满的!

于是他打了下面的暴力:(C++ 代码)

typedef long long ll;
bool check(ll x){
    if(x == 1) return false;
    for(ll i = 2; i < x; i++)
        if(x % i == 0) return false;
    return true;
}
int main(){
    ll n, ans = 0;
    cin >> n;
    for(ll i = 1; i <= n; i++)
        if(check(i)) ans++;
    cout << ans << endl;
}

虽然这个程序复杂度跑不满 O(n2)O(n^2),但是它还是毫无疑问地挂了。

nantf 不服气,他把 check 函数改写了一下:

typedef long long ll;
ll cnt = 0;
bool check(ll x){
    if(x == 1) return false;
    for(ll i = 2; i < x; i++){
        cnt++;
        if(x % i == 0) return false;
    }
    return true;
}

众所周知程序结束时 cntcnt 的值能反应程序的实际复杂度。

所以 nantf 找到了你,想让你帮忙算一下程序结束时 cntcnt 的值。不需要考虑溢出。


以上是一年半前 nantf 的惨痛回忆。

现在 nantf 已经会做这题了,但他现在对这个 cntcnt 很感兴趣,想要计算它的值。

nantf 当然知道怎么做啦!但是他想考考你……

另外,nantf 已经不关心这个程序的时间复杂度了,于是他决定让你求出 cntcnt2019060120190601(一个质数)取模的值。

输入格式

仅一行,包含一个正整数 nn

输出格式

仅一行,输出 cntcnt2019060120190601 取模的值。不需要考虑溢出。

样例 1

10
15
20190601
10608902

数据范围与提示

对于 10%10\% 的数据,1n1021\le n\le 10^2

对于 20%20\% 的数据,1n1031\le n\le 10^3

对于 40%40\% 的数据,1n1071\le n\le 10^7

对于 70%70\% 的数据,1n1091\le n\le 10^9

对于 100%100\% 的数据,1n10111\le n\le 10^{11}