這篇文章姑且叫做小總結大雜燴吧(大霧)
BZOJ 3930
題意
從區間 [L,H] 中選取 N 個整數,求它們的最大公約數為 K 的方案總數,答案 mod1e9+7 .
1≤N,K≤1e9,1≤L≤H≤1e9,H−L≤1e5 .
推導
就是莫比烏斯反演最正常的套路了
記 f(i) 為 gcd=i 的方案總數, F(i) 為 i|gcd 的方案總數,顯然有
F(i)=∑i|dgcd(d)
反演得 f(i)=∑i|dμ(di)F(d)
題目裡要求的即為
f(K)=∑K|dμ(dK)F(d)=∑i=1⌊HK⌋μ(i)F(ik)
注意:這裡 i 也就是 倍數 的下界是從 1 開始,而不是從 ⌈LK⌉ 開始。道理很顯然,取數的範圍的下界為 L 并不意味着 gcd 的下界也要為 L 啊。(智障到不忍回顧Orz)
F 很好求,即
F(x)=(⌊HK⌋−⌈LK⌉+1)n
也可寫作 F(x)=(⌊HK⌋−⌊L−1K⌋)n
接下來就是很顯然的分塊搞一搞了。
且慢……你說什麼範圍有 1e9 ?那還怎麼線性篩?
那就先來看另一道題吧~
51nod 1244
題意
求莫比烏斯函數之和,範圍 n≤1e10
參考
淺談一類積性函數的字首和 ——skywalkert
推導
我們有
∑d|nμ(d)=[n==1]
将左邊拆開來 μ(n)+∑d|n,d<nμ(d)=[n==1]
移過去 μ(n)=[n==1]−∑d|n,d<nμ(d)
求個和
∑i=1nμ(i)=∑i=1n[i==1]−∑i=1n∑d|i,d<iμ(d)=1−∑i=1n∑d|i,d<iμ(d)=1−∑k=2n∑d=1⌊nk⌋μ(d)
記 M(n)=∑ni=1μ(i) ,上式可化為 M(n)=1−∑k=2nM(⌊nk⌋)
很顯然就可以遞歸求解了。
具體做的時候設個門檻值 1e7 篩一部分算一部分。
奇怪的(…)延伸
其實這部分起初叫做:上面推導沒看明白的看這裡QWQ
為什麼
∑i=1n∑d|i,d<iμ(d)=∑k=2n∑d=1⌊nk⌋μ(d)
呢?
我們一般将裡面的部分提前的時候提的是枚舉的 因子 d ,這樣左邊就化為∑d=1n∑i=2⌊nd⌋μ(d)
右式中 d 的含義沒有變,i 則是枚舉的 d 的 倍數。繼續化下去=∑d=1nμ(d)∑i=2⌊nd⌋=∑d=1nμ(d)(⌊nd⌋−1)
這…好像并沒有什麼用處呢…。
現在我們考慮提前 倍數,則得到
∑k=2n∑d=1⌊nk⌋μ(d)
其中 k 的含義為 倍數,d 還是表示因子,這樣就得到了有用的可以用來遞推的式子了(撒花)。
真是神奇啊(大霧)
之前各種看人家的部落格各種看不懂嘤嘤嘤
不過我們也有一些收獲。
[n==1]=∑d|nμ(d)
兩邊求和
1=∑i=1n[i==1]=∑i=1n∑d|iμ(d)=∑d=1n∑i=1⌊nd⌋μ(d)=∑d=1nμ(d)∑i=2⌊nd⌋=∑d=1nμ(d)⌊nd⌋
也就是說 ∑d=1nμ(d)⌊nd⌋=1
哇世界真奇妙(大霧)姑且當成一個奇怪的結論吧~
Code
#include <bits/stdc++.h>
#include <map>
#define maxn 10000010
#define maxm maxn + 10
using namespace std;
typedef long long LL;
map<LL, LL> sum;
int prime[maxm], mu[maxm];
bool check[maxm];
void init() {
int tot = ; mu[] = ;
for (int i = ; i <= maxn; ++i) {
if (!check[i]) {
prime[tot++] = i;
mu[i] = -;
}
for (int j = ; j < tot; ++j) {
if (i * prime[j] > maxn) break;
check[i * prime[j]] = true;
if (i % prime[j] == ) {
mu[i * prime[j]] = ;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = ; i <= maxn; ++i) mu[i] += mu[i - ];
}
LL mu_sum(LL x) {
if (x <= maxn) return mu[x];
if (sum.find(x) != sum.end()) return sum[x];
LL le, ri, ret = ;
for (LL i = ; i <= x; i = ri + ) {
le = i, ri = x / (x / i);
ret += (ri - le + ) * mu_sum(x / i);
}
return sum[x] = - ret;
}
LL a, b;
void work() {
printf("%lld\n", mu_sum(b) - mu_sum(a - ));
}
int main() {
init();
while (scanf("%lld%lld", &a, &b) != EOF) work();
return ;
}
BZOJ 3930 續
有了上一題的基礎,這道題就好寫了
Code
#include <bits/stdc++.h>
#include <map>
#define maxn 10000010
#define maxm maxn + 10
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
const LL mod = +;
map<LL, LL> sum;
int prime[maxm], mu[maxm];
bool check[maxm];
void init() {
int tot = ; mu[] = ;
for (int i = ; i <= maxn; ++i) {
if (!check[i]) {
prime[tot++] = i;
mu[i] = -;
}
for (int j = ; j < tot; ++j) {
if (i * prime[j] > maxn) break;
check[i * prime[j]] = true;
if (i % prime[j] == ) {
mu[i * prime[j]] = ;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = ; i <= maxn; ++i) mu[i] += mu[i - ];
}
LL mu_sum(LL x) {
if (x <= maxn) return mu[x];
if (sum.find(x) != sum.end()) return sum[x];
LL le, ri, ret = ;
for (LL i = ; i <= x; i = ri + ) {
le = i, ri = x / (x / i);
ret = (ret + (ri - le + ) * mu_sum(x / i) + mod) % mod;
}
return sum[x] = ( - ret + mod) % mod;
}
LL poww(LL a, LL b) {
LL ret = ;
while (b) {
if (b & ) ret = ret * a % mod;
a = a * a % mod;
b >>= ;
}
return ret;
}
LL n, k, l, h;
LL F(LL d) { return poww(h / d - (l-) / d, n); }
void work() {
LL hi = h / k;
LL ans = , le, ri;
for (LL i = ; i <= hi; i = ri + ) {
LL temp = i * k;
le = i, ri = min(h / (h / temp), (l-) / temp ? (l-) / ((l-) / temp) : inf) / k;
ans = (ans + mod + (mu_sum(ri) - mu_sum(le - ) + mod) % mod * F(temp) % mod) % mod;
}
ans = (ans + mod) % mod;
printf("%lld\n", ans);
}
int main() {
init();
while (scanf("%lld%lld%lld%lld", &n, &k, &l, &h) != EOF) work();
return ;
}
BZOJ 2301
題意
求
∑x=ab∑y=cd[gcd(x,y)=k]
(低配版的BZOJ 3930)
推導
即求
∑i=1n∑j=1m[gcd(i,j)=k]
再容斥一下即可。
因為 gcd(i,j)=k ,是以 gcd(ik,jk)=1 ,是以上式可化為 ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd(i,j)=1]
即 ∑d=1min(⌊nk⌋,⌊mk⌋)μ(d)∑i=1⌊nkd⌋∑j=1⌊mkd⌋
即 ∑d=1min(⌊nk⌋,⌊mk⌋)μ(d)⌊nkd⌋⌊mkd⌋
分塊搞一搞就行了。
Code
#include <bits/stdc++.h>
#define maxn 50000
typedef long long LL;
using namespace std;
int kas, prime[maxn + ], mu[maxn + ], pre[maxn];
bool check[maxn + ];
void mobius() {
int tot = ;
mu[] = ;
for (int i = ; i <= maxn; ++i) {
if (!check[i]) {
prime[tot++] = i;
mu[i] = -;
}
for (int j = ; j < tot; ++j) {
if (i * prime[j] > maxn) break;
check[i * prime[j]] = true;
if (i % prime[j] == ) {
mu[i * prime[j]] = ;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = ; i <= maxn; ++i) pre[i] = pre[i - ] + mu[i];
}
LL calc(int c, int d) {
if (c > d) swap(c, d);
LL ans = ;
int le, ri;
for (int i = ; i <= c; i = ri + ) {
le = i, ri = min(c / (c / i), d / (d / i));
ans += L * (pre[ri] - pre[le - ]) * (c / i) * (d / i);
}
return ans;
}
void work() {
int a, b, c, d, k;
scanf("%d%d%d%d%d", &a, &c, &b, &d, &k);
LL tot1 = calc(c / k, d / k), tot2 = calc(c / k, (b-) / k),
tot3 = calc((a-) / k, d / k), tot4 = calc((a-) / k, (b-) / k);
printf("%lld\n", tot1 - tot2 - tot3 + tot4);
}
int main() {
mobius();
int T;
scanf("%d", &T);
while (T--) work();
return ;
}