头部背景图片
Decaku 's Blog |
Decaku 's Blog |

类欧几里得

几何意义为求一个梯形内的整点的个数
常用的类欧有以下三个
$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor (ai+b)/c \rfloor$
$g(a,b,c,n)=\sum_{i=0}^{n}i\lfloor(ai+b)/c \rfloor$
$h(a,b,c,n)=\sum_{i=0}^{n}\lfloor(ai+b)/c\rfloor^{2}$

时间复杂度:对于$n=10^{9}$的询问,$f$为$log(n)$,$g$和$h$在$10^{7}$左右。
一个常见套路:二进制下判断一个数$x$第$k$位是否为1等价于$x/2^{k}-2(x/2^{k+1})$。

一道例题:
求$\sum_{i=0}^{n}\sum_{j=0}^{n}(ij) \oplus c $, $c和n$是给定常数
分析:假设枚举$i$,则问题其实是求一个等差数列和$c$异或后的值的和,不妨对$c$按位考虑,那么问题其实就是转化成求一个等差数列前n项里(从0开始)第$k$位是0/1的有几项,然后把贡献加到答案里去这题就做完了。
根据上面的所讲过的经典套路,一个形如$X=Ai+B$的等差数列第k位是1的个数
$Ans_k=\sum_{i=1}^n(\lfloor(Ai+b)/2^k\rfloor-2\lfloor(Ai+b)/2^{k+1}\rfloor) \\=f(A,B,2^k,n)-f(A,B,2^{k+1},n)$

综上,总复杂度是$nloglog$的。
关于求等差数列二进制数位1的个数的题还有$JZOJ3492 数数(count)以及【GDOI2018模拟8.8】超级绵羊异或$。

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define rep(i,a,b) for(int i=a;i<=(int)b;++i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const ll mod=1e9+7;

ll f(ll a,ll b,ll c,ll n){
if(a==0){
return (n+1)*(b/c);
}
if(a<c && b<c){
ll m=(a*n+b)/c;
if(m==0)return 0;
return n*m-f(c,c-b-1,a,m-1);
}
return f(a%c,b%c,c,n)+(n+1)*(b/c)+((n+1)/(1+(n&1)))*(n/(2-(n&1)))*(a/c);
}

int main()
{
ll n,c;
cin>>n>>c;
ll ans=0;
for(ll i=0; i<=n; ++i)
{
for(ll k=0; k<=34; ++k)
{
ll tem=f(i,0ll,(1ll<<k),n)-2*f(i,0ll,1ll<<(k+1),n);
if((1ll<<k)&c) {ans+=(n+1-tem)*(1ll<<k)%mod;ans%=mod;}
else {ans+=tem*(1ll<<k)%mod;ans%=mod;}
}
}
cout<<ans<<endl;
}

一道难题:bzoj3817
求$\sum_{i=1}^{n}(-1)^{\lfloor i \sqrt{r} \rfloor}$,$n有10^9$
参考题解:https://www.luogu.org/problemnew/solution/P5172

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define gec getchar
using namespace std;
typedef long long ll;
char ch;
bool fl;
inline void read(int &a){
for(fl=0,ch=gec();ch<'0'||ch>'9';ch=gec()) fl|=(ch=='-');
for(a=0;ch>='0'&&ch<='9';ch=gec())a=(a<<3)+(a<<1)+(ch^'0');
if(fl)a=-a;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int n,R,T;
double x;
int Solve(int n,int a,int b,int c){
if(!n)return 0;
int tmp=gcd(gcd(a,b),c);
a/=tmp;b/=tmp;c/=tmp;
tmp=(b*x+c)/a;c-=tmp*a;
int Sum=((ll)n*(n+1)>>1)*tmp;
int P=(b*x+c)/a*n;
return Sum-Solve(P,b*b*R-c*c,a*b,-a*c)+(ll)P*n;
}
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&R);
x=sqrt(R);
int w=x;
if(w*w==R) printf("%d\n",(w&1)?((n&1)?-1:0):n);
else printf("%d\n",n+(Solve(n,2,1,0)<<2)-(Solve(n,1,1,0)<<1));
}
return 0;
}
avatar Decaku 菜菜菜