我是靠谱客的博主 寒冷滑板,这篇文章主要介绍SPOJ 20713 DIVCNT2 - Counting Divisors (square),现在分享给大家,希望可以做个参考。

DIVCNT2 - Counting Divisors (square)

#sub-linear  #dirichlet-generating-function

 

Let sigma_0(n)σ0​​(n) be the number of positive divisors of nn.

For example, sigma_0(1) = 1σ0​​(1)=1, sigma_0(2) = 2σ0​​(2)=2 and sigma_0(6) = 4σ0​​(6)=4.

LetS_2(n) = sum _{i=1}^n sigma_0(i^2).S2​​(n)=i=1n​​σ0​​(i2​​).

Given NN, find S_2(N)S2​​(N).

Input

First line contains TT (1 le T le 100001T10000), the number of test cases.

Each of the next TT lines contains a single integer NN. (1 le N le 10^{12}1N1012​​)

Output

For each number NN, output a single line containing S_2(N)S2​​(N).

Example

Input

复制代码
1
5
1
2
3
10
100

Output

复制代码
1
1
4
7
48
1194

Explanation for Input

S_2(3) = sigma_0(1^2) + sigma_0(2^2) + sigma_0(3^2) = 1 + 3 + 3 = 7S2​​(3)=σ0​​(12​​)+σ0​​(22​​)+σ0​​(32​​)=1+3+3=7

Information

There are 6 Input files.

- Input #1: 1 le N le 100001N10000, TL = 1s.

- Input #2: 1 le T le 800, 1 le N le 10^{8}1T800, 1N108​​, TL = 20s.

- Input #3: 1 le T le 200, 1 le N le 10^{9}1T200, 1N109​​, TL = 20s.

- Input #4: 1 le T le 40, 1 le N le 10^{10}1T40, 1N1010​​, TL = 20s.

- Input #5: 1 le T le 10, 1 le N le 10^{11}1T10, 1N1011​​, TL = 20s.

- Input #6: T = 1, 1 le N le 10^{12}T=1, 1N1012​​, TL = 20s.

My C++ solution runs in 5.3 sec. (total time)

Source Limit is 6 KB.

 

 

很迷的函数题。

如何求 d(i^2)?

d(i^2)= (2*a1+1)(2*a2+1)(2*a3+1)...(2*ak+1)

我们考虑一下选哪些质因子的集合,上式

=Σ2^|S| *π a[i] ,i属于S

=Σ(p|i)  2^w(p)。

其中w(x)为x的质因子数。

然后发现2^w(x)=Σ(i|x)  μ^2(i)

 

所以ANS= Σμ^2(i) *Σd(j)  ,其中1<=i<=n,1<=j<=(n/i)。

复制代码
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
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h> #define ll long long using namespace std; int zs[10000005],t=0,T,sq[50000005]; int miu[50000005],low[50000005],maxn; bool v[50000005]; ll d[50000005],n; inline void init(){ miu[1]=1,d[1]=1,low[1]=1; for(int i=2;i<=maxn;i++){ if(!v[i]) zs[++t]=i,miu[i]=-1,d[i]=2,low[i]=i; for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){ v[u]=1; if(!(i%zs[j])){ low[u]=low[i]*zs[j]; if(low[i]==i) d[u]=d[i]+1; else d[u]=d[low[u]]*d[i/low[i]]; break; } low[u]=zs[j]; d[u]=d[i]<<1; miu[u]=-miu[i]; } } for(int i=1;i<=maxn;i++) d[i]+=d[i-1]; for(int i=1;i<=maxn;i++) sq[i]=sq[i-1]+miu[i]*miu[i]; } inline ll getsq(ll x){ if(x<=maxn) return sq[x]; ll an=0; for(int i=1;i*(ll)i<=x;i++){ an+=miu[i]*(x/(i*(ll)i)); } return an; } inline ll getd(ll x){ if(x<=maxn) return d[x]; ll an=0; for(ll i=1,j,now;i<=x;i=j+1){ now=x/i,j=x/now; an+=(j-i+1)*now; } return an; } inline ll query(ll x){ ll an=0; for(ll i=1,j,now;i<=x;i=j+1){ now=x/i,j=x/now; an+=(getsq(j)-getsq(i-1))*getd(now); } return an; } int main(){ scanf("%d",&T); if(T>800) maxn=1000000; else maxn=50000000; init(); while(T--){ scanf("%lld",&n); printf("%lldn",query(n)); } return 0; }

  

 

转载于:https://www.cnblogs.com/JYYHH/p/8511216.html

最后

以上就是寒冷滑板最近收集整理的关于SPOJ 20713 DIVCNT2 - Counting Divisors (square)的全部内容,更多相关SPOJ内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(77)

评论列表共有 0 条评论

立即
投稿
返回
顶部