1.1 Discription
小暢和阿尼巴是好朋友。
如果你趕著 AK,請(qǐng)手動(dòng)跳至最后一行
阿尼巴特別喜歡質(zhì)數(shù)。
他認(rèn)為質(zhì)數(shù)就是有智慧的數(shù),如果經(jīng)常玩質(zhì)數(shù)的話一定會(huì)變得像小暢
一樣充滿智慧。
然而這次他在玩一個(gè)數(shù)的時(shí)候,不小心把它給玩散了
這個(gè)數(shù)散落得滿地都是,以至于喜歡跳舞的小暢都沒有地方跳街舞了!!!
小暢十分氣憤,恰好他知道阿尼巴喜歡質(zhì)數(shù)
于是就想出一道質(zhì)數(shù)的題目來氣氣他
“今天,我是作為一個(gè)長者在這里跟你講話的。畢竟你啊,too young,
too simple, sometimes naive。你以為玩質(zhì)數(shù)就可以變得像我一樣滿腹
智慧嗎?想變的有智慧,先讓我作為數(shù)論王者來考考你。怕你自卑,就
不考你多項(xiàng)式 exp,ln,sqrt, 求逆那種稍微小學(xué)一點(diǎn)的內(nèi)容了。設(shè) f (i) 為
i 的不同的質(zhì)因子的個(gè)數(shù)。一個(gè)數(shù) i 它散落在地上的方案就是 2 f (i) ,你
啊現(xiàn)在給我求出 1 ? n 所有數(shù)散落在地上的方案和。不然,既然不讓我
跳舞, 就不得不好好懲罰你了呢”
咳咳,說人話,就是讓你求$sum_{i=1}^{n}2^{f(i)}$,其中 f (i) 表示 i 的不同的質(zhì)因子的個(gè)數(shù)
答案對(duì) 998244353 取模
Input format
第一行一個(gè)正整數(shù) n
Output format
輸出一行,表示答案
Sample Input
2
Sample Input
3
Hint
20% 的數(shù)據(jù)滿足 n ≤ 10^6
100% 的數(shù)據(jù)滿足 1 ≤ n ≤ 10^12

首先$2^{f(x)}$可以看作把x的質(zhì)因數(shù)分配給$i$和$j$，顯然$gcd(i,j)=1$

所以$sum_{i=1}^{n}sum_{d|i}[gcd(d,frac{i}ze8trgl8bvbq)=1]$

$sum_{i=1}^{n}sum_{d|i}sum_{p|d wedge p|frac{i}ze8trgl8bvbq}mu(p)$

$g(i)$表示$i$的約數(shù)個(gè)數(shù)

$sum_{i=1}^{n}sum_{p^2|i}g(frac{i}{p^2})mu(p)$

$sum_{p=1}^{sqrt(n)}mu(p)sum_{i=1}^{frac{n}{p^2}}g(i)$

$sum_{i=1}^{frac{n}{p^2}}g(i)=sum_{i=1}^{frac{n}{p^2}}sum_{d|i}1$

交換一下變成$sum_{p=1}^{sqrt(n)}mu(p)sum_{i=1}^{frac{n}{p^2}}[frac{n}{p^2*d}]$

然后枚舉p套一個(gè)數(shù)論分塊就可以了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long lol;
 8 lol mu[1000001],n,lim,ans,Mod=998244353,pri[10000001],tot;
 9 bool vis[10000001];
10 lol query(lol x)
11 {lol pos,i;
12   lol sum=0;
13   for (i=1;i<=x;i=pos+1)
14     {
15       pos=x/(x/i);
16       sum+=(pos-i+1)*(x/i)%Mod;sum%=Mod;
17     }
18   return sum;
19 }
20 int main()
21 {lol i,j;
22   cin>>n;
23   lim=sqrt(n);
24   mu[1]=1;
25   for (i=2;i<=lim;i++)
26     {
27       if (vis[i]==0)
28     {
29       pri[++tot]=i;
30       mu[i]=-1;
31     }
32       for (j=1;j<=tot;j++)
33     {
34       if (1ll*i*pri[j]>lim) break;
35       vis[i*pri[j]]=1;
36       if (i%pri[j]==0)
37           break;
38       else mu[i*pri[j]]=-mu[i];
39     }
40     }
41   for (i=1;i<=lim;i++)
42     {
43       ans+=mu[i]*query(n/(i*i));
44       ans=(ans+Mod)%Mod;
45     }
46   cout<<ans;
47 }

總結(jié)

以上是生活随笔為你收集整理的质数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。