- 类欧几里得可以等价于求 (y=(ax+b)/c) 这条直线和 (x=0,y=0,x=n) 围成的直角梯形内整点个数
前置芝士：
-
-
用途：快速求出以下式子的值
(displaystyle f(a,b,c,n)=sum_{i=0}^nlfloor frac{ai+b}{c} floor)
(displaystyle g(a,b,c,n)=sum_{i=0}^n ilfloor frac{ai+b}{c} floor)
(displaystyle h(a,b,c,n)=sum_{i=0}^nlfloor frac{ai+b}{c} floor^2)(记 (m=lfloor frac{an+b}{c} floor))
推柿子
-
求 (f)
-
(a>c or b>c)
(f(a,b,c,n)=f(amod c,bmod c,c,n)+frac{n(n+1)}{2}lfloorfrac{a}{c} floor+(n+1)lfloorfrac{b}{c} floor)
-
(a<c and b<c)
[displaystyle f(a,b,c,n)=sum_{i=0}^nsum_{j=1}^m[jle lfloor frac{ai+b}{c} floor] \ =sum_{i=0}^nsum_{j=0}^{m-1}[j+1le lfloor frac{ai+b}{c} floor] \ =sum_{i=0}^nsum_{j=0}^{m-1}[cj+c-ble ai] \ =sum_{i=0}^nsum_{j=0}^{m-1}[cj+c-b-1< ai] \ =sum_{i=0}^nsum_{j=0}^{m-1}[frac{cj+c-b-1}{a}<i] \ =sum_{j=0}^{m-1} n-lfloorfrac{cj+c-b-1}{a} floor \ =n*m-f(c,c-b+1,a,m-1) ]
-
-
求 (g)
-
(a>c or b>c)
(g(a,b,c,n)=g(amod c,bmod c,c,n)+frac{n(n+1)(2n+1)}{6}lfloorfrac{a}{c} floor+frac{n(n+1)}{2}lfloorfrac{b}{c} floor)
-
(a<c and b<c)
[displaystyle g(a,b,c,n)=sum_{i=0}^nisum_{j=1}^m[jle lfloor frac{ai+b}{c} floor] \ =sum_{i=0}^nisum_{j=0}^{m-1}[j+1le lfloor frac{ai+b}{c} floor] \ =sum_{i=0}^nisum_{j=0}^{m-1}[cj+c-ble ai] \ =sum_{i=0}^nisum_{j=0}^{m-1}[cj+c-b-1< ai] \ =sum_{i=0}^nisum_{j=0}^{m-1}[frac{cj+c-b-1}{a}<i] \ 由于 i 的取值是一个等差数列，首项为 lfloorfrac{cj+c-b-1}{a} floor+1 末项为 n \ =sum_{j=0}^{m-1}frac{(n-lfloorfrac{cj+c-b-1}{a} floor)(n+lfloorfrac{cj+c-b-1}{a} floor+1)}{2} \ =frac{1}{2}sum_{j=0}^{m-1}(n(n+1)-lfloorfrac{cj+c-b-1}{a} floor-lfloorfrac{cj+c-b-1}{a} floor^2) \ =frac{mn(n+1)-f(c,c-b+1,a,m-1)-h(c,c-b+1,a,m-1)}{2} ]
-
-
求 (h)
-
(a>c or b>c)
(h(a,b,c,n)=h(amod c,bmod c,c,n)\+frac{n(n+1)(2n+1)}{6}lfloorfrac{a}{c} floor^2+(n+1)lfloorfrac{b}{c} floor^2\+2lfloorfrac{b}{c} floor f(amod c,bmod c,c,n)+2lfloorfrac{a}{c} floor g(amod c,bmod c,c,n)+lfloorfrac{b}{c} floorlfloorfrac{a}{c} floor n(n+1))
-
(a<c and b<c)
为了方便计算我们，将 (n^2) 转化一下，(n^2=2*frac{n(n+1)}{2}-n=-n+2sum_{i=0}^ni)
[displaystyle h(a,b,c,n)=sum_{i=0}^n(-lfloor{frac{ai+b}{c}} floor+2sum_{j=0}^{lfloor{frac{ai+b}{c}} floor}j) \ 将括号内部的两个式子分开计算 \ =2sum_{j=0}^{m-1}j+1sum_{i=0}^n[lfloor{frac{ai+b}{c}} floorge j+1]-f(a,b,c,n) \ 不想推了/kk \ h(a,b,c,n)=m(m+1)n-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n) ] -
代码：
这式子能给我写吐了/ee
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
long long read()
{
long long x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const long long mod = 998244353;
const long long inv2 = 499122177;
const long long inv6 = 166374059;
struct node
{
long long f,g,h;
node(){}
node(long long f,long long g,long long h){}
};
node solve(long long a,long long b,long long c,long long n)
{
node ans,tmp;
if(!a)
{
n%=mod;
ans.f=(n+1)*(b/c)%mod;
ans.g=(b/c)*n%mod*(n+1)%mod*inv2%mod;
ans.h=(n+1)*(b/c)%mod*(b/c)%mod;
return ans;
}
if(a>=c||b>=c)
{
ans=solve(a%c,b%c,c,n);
n%=mod;
ans.h=( ans.h
+1ll*n*(n+1)%mod*(2*n%mod+1)%mod*inv6%mod*(a/c)%mod*(a/c)%mod
+(n+1)%mod*(b/c)%mod*(b/c)%mod
+2*(b/c)%mod*ans.f%mod
+2*(a/c)%mod*ans.g%mod
+n*(n+1)%mod*(a/c)%mod*(b/c)%mod
) %mod;
ans.f=(ans.f+n*(n+1)%mod*inv2%mod*(a/c)%mod+(n+1)*(b/c)%mod)%mod;
ans.g=(ans.g+n*(n+1)%mod*(2*n+1)%mod*inv6%mod*(a/c)%mod+n*(n+1)%mod*inv2%mod*(b/c))%mod;
return ans;
}
long long m=(a*n+b)/c;
tmp=solve(c,c-b-1,a,m-1);
n%=mod;m%=mod;
ans.f=(n*m%mod-tmp.f+mod)%mod;
ans.g=(m*n%mod*(n+1)%mod-tmp.f+mod-tmp.h+mod)%mod*inv2%mod;
ans.h=(m*n%mod*(m+1)%mod-2*((tmp.f+tmp.g)%mod)%mod+mod-ans.f+mod)%mod;
return ans;
}
void work()
{
long long t,n,a,b,c;
node ans;
t=read();
while(t--)
{
n=read();a=read();b=read();c=read();
ans=solve(a,b,c,n);
printf("%lld %lld %lld
",ans.f,ans.h,ans.g);
}
}
}
int main()
{
zzc::work();
return 0;
}