SPOJ 19975 Amazing Prime Sequence (hard)

发表于 | 分类于 |

emmmm 其实原数据限制是这样的：

There are 6 Input files.

  • Input #0: \(1 \le T \le 10000, 1 \le N \le 10000\), TL = 1s.
  • Input #1: \(1 \le T \le 1000, 1 \le N \le 10^8\), TL = 20s.
  • Input #2: \(1 \le T \le 200, 1 \le N \le 10^9\), TL = 20s.
  • Input #3: \(1 \le T \le 40, 1 \le N \le 10^{10}\), TL = 20s.
  • Input #4: \(1 \le T \le 7, 1 \le N \le 10^{11}\), TL = 20s.
  • Input #5: \(T = 1, 1 \le N \le 12345678910111\), TL = 20s.

首先会 Min_25 筛的都知道 Min_25 筛求质数处点值和时本质上是埃筛，只是一次性从最小质因子筛去了一批数。
这个时候就可以发现很容易得知对于一个质数，有多少个数的最小质因子是它。
计算贡献即可。

然而我们又发现质数本身的贡献没有算。
再算一下质数的和即可。
都是基本操作。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cmath>
using namespace std;
const long long N = 1234567891011;
const int MX = 1111112;
int T;
long long n;
int lim;
int vis[MX + 5],cnt,prime[MX + 5];
unsigned long long Gprime[MX + 5];
int le[MX + 5],ge[MX + 5],tot;
long long lis[2 * MX + 5];
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
unsigned long long G[2 * MX + 5][2],F[2 * MX + 5];
int main()
{
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            prime[++cnt] = i,Gprime[cnt] = Gprime[cnt - 1] + i;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%lld",&n),lim = sqrt(n),tot = 0;
        for(register long long l = 1,r;l <= n;l = r + 1)
        {
            r = n / (n / l);
            lis[id(n / l) = ++tot] = n / l;
            G[tot][0] = n / l - 1,G[tot][1] = (n / l + 2) & 1 ? (n / l - 1) / 2 * (n / l + 2) : (n / l + 2) / 2 * (n / l - 1),F[tot] = 0;
        }
        for(register int k = 1;k <= cnt && prime[k] <= lim;++k)
        {
            int p = prime[k];
            long long s = (long long)p * p;
            for(register int i = 1;lis[i] >= s && i <= tot;++i)
                F[i] += p * (G[id(lis[i] / p)][0] - (k - 1)),
                G[i][0] -= G[id(lis[i] / p)][0] - (k - 1),
                G[i][1] -= p * (G[id(lis[i] / p)][1] - Gprime[k - 1]);
        }
        printf("%llu\n",F[1] + G[1][1]);
    }
}