題目描述

很久很久以前，有一只神犇叫yzy; 很久很久之后，有一只蒟蒻叫l(wèi)ty;

輸入

請(qǐng)你讀入一個(gè)整數(shù)N;1<=N<=1E9,A、B模1E9+7;

輸出

請(qǐng)你輸出一個(gè)整數(shù)A=\sum_{i=1}^N{\mu (i^2)}; 請(qǐng)你輸出一個(gè)整數(shù)B=\sum_{i=1}^N{\varphi (i^2)};

樣例輸入

1

樣例輸出

1
1

---

題解

杜教篩

第一問(wèn)的答案毫無(wú)疑問(wèn)肯定是1（wow~ ⊙o⊙），畢竟除了i=1以外質(zhì)因子的冪次一定大于等于2。

對(duì)于第二問(wèn)歐拉函數(shù)Φ(i^2)=iΦ(i)，因?yàn)閷分解質(zhì)因數(shù)，質(zhì)因子的冪次一定大于等于2且為偶數(shù)。我們計(jì)算歐拉函數(shù)時(shí)，如果出現(xiàn)p^a，那么是算進(jìn)答案(p-1)*p^(a-1)。如果把p^(a/2)的部分取出，剩下的是Φ(i)的部分，而取出的是i的部分，因此答案是∑iΦ(i)。

現(xiàn)在只要求∑iΦ(i)即可。

我們把它與id求卷積，發(fā)現(xiàn)形式就是n^2。

所以有：

其中重點(diǎn)是因子與乘積的轉(zhuǎn)化，在公式第2、3行將枚舉乘積i轉(zhuǎn)化為枚舉2行的i/d和d，即3行的i和j。

先預(yù)處理出n^2/3的部分，超過(guò)的部分對(duì)于每個(gè)n/i進(jìn)行遞歸，記憶化搜索，使用map儲(chǔ)存。

總時(shí)間復(fù)雜度O(n^2/3logn)。

這里有一個(gè)小細(xì)節(jié)：除的數(shù)固定并且很小時(shí)不需要求逆元，直接將模數(shù)擴(kuò)大相應(yīng)倍數(shù)，正常取模，最后再模下去。

#include <cstdio> #include <map> #define N 1000010 #define mod 6000000042ll using namespace std; typedef long long ll; map<ll , ll> f; map<ll , ll>::iterator it; ll m = 1000000 , phi[N] , prime[N] , tot , sum[N]; bool np[N]; ll s1(ll l , ll r) {return (l + r) * (r - l + 1) % mod / 2; } ll s2(ll x) {return x * (x + 1) % mod * (2 * x + 1) % mod / 6; } ll query(ll n) {if(n <= m) return sum[n];it = f.find(n);if(it != f.end()) return it->second;ll ans = s2(n) , i , last;for(i = 2 ; i <= n ; i = last + 1) last = n / (n / i) , ans = (ans - s1(i , last) * query(n / i) % mod + mod) % mod;f[n] = ans;return ans; } int main() {ll i , j , n;phi[1] = sum[1] = 1;for(i = 2 ; i <= m ; i ++ ){if(!np[i]) phi[i] = i - 1 , prime[++tot] = i;for(j = 1 ; j <= tot && i * prime[j] <= m ; j ++ ){np[i * prime[j]] = 1;if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j];break;}else phi[i * prime[j]] = phi[i] * (prime[j] - 1);}sum[i] = (sum[i - 1] + i * phi[i]) % mod;}scanf("%lld" , &n);printf("1\n%lld\n" , query(n) % 1000000007);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/6957885.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj4916】神犇和蒟蒻 杜教筛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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