本文主要是介绍写了个暴力加了点剪枝就过了结果发现是复杂度级别的优化.gif，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

题目描述
对于所有 x ∈ [ A , B ] ,    y ∈ [ C , D ] x\in[A,B],\;y\in[C,D] x∈[A,B],y∈[C,D] 的二元组 x , y x,y x,y，记 d = gcd ⁡ ( x , y ) d=\gcd(x,y) d=gcd(x,y)，如果 x + y d ⩽ V = 999 {x+y\over d}\leqslant V=999 dx+y​⩽V=999，那么将计数器加上 x + y d {x+y\over d} dx+y​ 。

请求出最后计数器的值。

数据范围与提示
A , B , C , D ⩽ 1 0 12 A,B,C,D\leqslant 10^{12} A,B,C,D⩽1012 。但是事实证明这是误导信息。

思路

先讲我的思路。因为大家一看正解，就觉得我的做法是傻子。

为了方便，容斥一下，只考虑 x ⩽ A x\leqslant A x⩽A 和 y ⩽ B y\leqslant B y⩽B 的约束。一看这个 1 0 12 10^{12} 1012，肯定联想 A \sqrt A A ​ 啊，整除分块？试一试吧。

考虑枚举 d d d，那么 x d , y d {x\over d},{y\over d} dx​,dy​ 有一个范围。但是还要保证二者互质，所以利用莫比乌斯函数。可以得到式子是
∑ d ∑ p μ ( p ) ∑ x ⩽ ⌊ A d p ⌋ ∑ y ⩽ ⌊ B d p ⌋ [ x + y ⩽ ⌊ V p ⌋ ] ( x p + y p ) \sum_{d}\sum_{p} \mu(p) \sum_{x\leqslant\lfloor{A\over dp}\rfloor} \sum_{y\leqslant\lfloor{B\over dp}\rfloor} \left[x+y\leqslant\left\lfloor{V\over p}\right\rfloor\right] (xp+yp) d∑​p∑​μ(p)x⩽⌊dpA​⌋∑​y⩽⌊dpB​⌋∑​[x+y⩽⌊pV​⌋](xp+yp)

那么显然，当 p p p 一定时，后面 x , y x,y x,y 的范围只由 d d d 决定，并且是整除分块的形式。枚举 p p p 则复杂度为 O ( V A ) \mathcal O(V\sqrt{A}) O(VA ​) 。

测试了一下，发现 A = 1 0 12 A=10^{12} A=1012 的运行速度极其慢。于是考虑剪枝。当 ⌊ A d p ⌋ ⩾ ⌊ V p ⌋ \lfloor{A\over dp}\rfloor\geqslant\lfloor{V\over p}\rfloor ⌊dpA​⌋⩾⌊pV​⌋ 时，这个范围就失去了意义，因为 x + y ⩽ ⌊ V p ⌋ x+y\leqslant\lfloor{V\over p}\rfloor x+y⩽⌊pV​⌋ 已经保证了这一点。所以就把这样的 d d d 拿出来统一计算。

那么，我们只需要计算 ⌊ A d p ⌋ < ⌊ V p ⌋ \lfloor{A\over dp}\rfloor<\lfloor{V\over p}\rfloor ⌊dpA​⌋<⌊pV​⌋ 的部分。由于我们是数论分块，本就会让 ⌊ A d p ⌋ \lfloor{A\over dp}\rfloor ⌊dpA​⌋ 的值每次不同，所以复杂度是 O ( ⌊ V p ⌋ ) \mathcal O(\lfloor{V\over p}\rfloor) O(⌊pV​⌋) 。注意我们要对 B B B 也进行同样的操作，才能保证复杂度。

诶，好像复杂度是 O ( V ln ⁡ V ) \mathcal O(V\ln V) O(VlnV) 的，搞定了？并且最终复杂度与 A A A 无关？

正解

枚举两个互质的数 x d , y d ∈ [ 0 , V ] {x\over d},{y\over d}\in[0,V] dx​,dy​∈[0,V]，根据 x , y x,y x,y 的范围可以求出 d d d 的范围，也就得到了这种方案的数量。时间复杂度 O ( V 2 ) \mathcal O(V^2) O(V2)，注意用二维数组存储 gcd ⁡ \gcd gcd，否则可能变为 O ( V 2 ln ⁡ V ) \mathcal O(V^2\ln V) O(V2lnV) 。

代码

代码实现中，我还对 V p , A p , B p \frac Vp,\frac Ap,\frac Bp pV​,pA​,pB​ 作了整除分块。虽然它实际上没太大用……

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int Mod = 1e9+7;
const int inv2 = (Mod+1)>>1;
const int V = 999;
int mu[V+1]; bool isPrime[V+1];
void sieve(){
	memset(isPrime+2,1,V-1);
	rep(i,1,V) mu[i] = 1;
	rep(i,2,V) if(isPrime[i]){
		mu[i] = -1;
		for(int j=2; j<=V/i; ++j){
			if(j%i == 0) mu[i*j] = 0;
			isPrime[i*j] = false;
			mu[i*j] = -mu[i*j];
		}
	}
}

int jb[V+1]; // a*(a+1)*(2*a+1)/6+a*(a+1)/2
int calc(int a,int b,const int &X){
	if(a+b < X) // never explode
		return ((b*a*(a+1)>>1)
			+(a*b*(b+1)>>1))%Mod;
	int res = (jb[a]+(X-a-1)*a*(a+1))%Mod;
	res += (jb[b]+(X-b-1)*b*(b+1))%Mod;
	res -= jb[X-a-1]; res -= jb[X-b-1];
	res = (res%Mod+Mod)%Mod;
	return int(int_(res)*inv2%Mod);
}
int wxk[V+1]; // prefix sum of mu[i]*i
int solve(int_ a0,int_ b0){
	if(a0 > b0) swap(a0,b0);
	int res = 0, end_p = min(a0,int_(V>>1));
	for(int p=1,rp; p<=end_p; p=rp+1){
		rp = min(a0/(a0/p),b0/(b0/p));
		const int X = V/p; // real boundary
		rp = min(rp,V/X); // keep the same
		int_ a = a0/p, b = b0/p;
		int_ l = a/(X-1)+1; // or X-1 <= a/l
		int_ ddg = b/(X-1); // or X-1 <= b/l
		int now = calc(X-1,X-1,X)*(l-1)%Mod;
		for(int_ r; l<=a; l=r){
			r = min(a/(a/l),b/(b/l))+1;
			if(b/l >= X-1) // useless
				r = min(ddg,a/(a/l))+1;
			int ta = min(a/l,int_(X-1));
			int tb = min(b/l,int_(X-1));
			now = (now+calc(ta,tb,X)*(r-l))%Mod;
		}
		int t = wxk[rp]-wxk[p-1];
		res = (res+int_(now)*t)%Mod;
	}
	return (res%Mod+Mod)%Mod;
}

int main(){
	rep(i,1,V) jb[i] = jb[i-1]+i*(i+1);
	sieve(); int_ a, b, c, d;
	rep(i,1,V) wxk[i] = wxk[i-1]+mu[i]*i;
	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
	int res = solve(b,d)+solve(a-1,c-1);
	res -= solve(a-1,d)+solve(b,c-1);
	printf("%d\n",(res%Mod+Mod)%Mod);
	return 0;
}

这篇关于写了个暴力加了点剪枝就过了结果发现是复杂度级别的优化.gif的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！