鲜花
从树论赶来的，感觉这个东西没什么用啊…QwQ
欧几里得
欧几里得算法
也称辗转相除法。
就是一个简单的式子：
gcd ( a , b ) = gcd ( b , a m o d b ) \gcd(a,b)=\gcd(b,a \bmod b)
g cd( a , b ) = g cd( b , a m o d b )
证明如下：
令 b = k a + r , g c d ( a , b ) = d 则有 d ∣ a , d ∣ b r = b − k a ⇒ b d − k a d = r d 由于左边显然为整数 ∴ r 和 a 的公约数相等 ∴ r 和 a 的最大公约数相等 \text{令 } b=ka+r\ ,\ gcd(a,b)=d\\
\text{则有 } d\ \vert\ a\ ,\ d\ \vert\ b\\
r=b-ka\Rightarrow \frac{b}{d} - \frac{ka}{d}=\frac{r}{d}\\
\text{由于左边显然为整数}\\
\therefore r\ \text{和 } a \text{ 的公约数相等}\\
\therefore r\ \text{和 } a \text{ 的最大公约数相等}
令 b = k a + r , g c d ( a , b ) = d 则有 d ∣ a , d ∣ b r = b − k a ⇒ d b − d k a = d r 由于左边显然为整数 ∴ r 和 a 的公约数相等 ∴ r 和 a 的最大公约数相等
证毕。
扩展欧几里得算法（exgcd）
裴蜀定理
定理
对于任意不全为 0 0 0 a , b a,b a , b x , y x,y x , y a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) a x + b y = g cd( a , b )
证明
令 d = gcd ( a , b ) , a = a 1 d , b = b 1 d d=\gcd(a,b),a=a_1d,b=b_1d d = g cd( a , b ) , a = a 1 d , b = b 1 d
则有 a 1 d x + b 1 d y = d ( a 1 x + b 1 y ) a_1dx+b_1dy=d(a_1x+b_1y) a 1 d x + b 1 d y = d ( a 1 x + b 1 y )
那么可以把证明转化为对于任意不全为 0 0 0 a , b a,b a , b gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 x , y x,y x , y a x + b y = 1 ax+by=1 a x + b y = 1 。
考虑模拟一遍欧几里得算法求 gcd ( a , b ) \gcd(a,b) g cd( a , b )
gcd ( a , b ) ⇒ gcd ( b , a m o d b ) ⇒ gcd ( a m o d b , b m o d ( a m o d b ) ) ⇒ ⋯ ⋯ \gcd(a,b)\Rightarrow\gcd(b,a\bmod b)\Rightarrow\gcd(a\bmod b,b\bmod(a\bmod b))\Rightarrow\cdots\cdots
g cd( a , b ) ⇒ g cd( b , a m o d b ) ⇒ g cd( a m o d b , b m o d ( a m o d b ) ) ⇒ ⋯ ⋯
发现很复杂，则把每一次的数记为 r 1 , r 2 , r 3 r_1,r_2,r_3 r 1 , r 2 , r 3
r m − 1 = r m q m r m − 2 = r m − 1 q m − 1 + r m ⋯ ⋯ r 1 = r 2 q 2 + r 3 a = r 1 q 1 + r 2 r_{m-1}=r_mq_m\\
r_{m-2}=r_{m-1}q_{m-1}+r_m\\\cdots\cdots\\
r_1=r_2q_2+r_3\\
a=r_1q_1+r_2
r m − 1 = r m q m r m − 2 = r m − 1 q m − 1 + r m ⋯ ⋯ r 1 = r 2 q 2 + r 3 a = r 1 q 1 + r 2
考虑带入 gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 r m = 1 r_m=1 r m = 1 q k q_k q k x k + 1 x_{k+1} x k + 1
⋯ ⇒ r m − 2 = r m − 1 x m + 1 ⇒ 1 = r m − 2 − x m r m − 1 \cdots\Rightarrow r_{m-2}=r_{m-1}x_{m}+1\Rightarrow 1=r_{m-2}-x_mr_{m-1}
⋯ ⇒ r m − 2 = r m − 1 x m + 1 ⇒ 1 = r m − 2 − x m r m − 1
继续带入。
r m − 3 = r m − 2 x m − 1 + r m − 1 ⇒ r m − 1 = r m − 3 − r m − 2 x m − 1 ⋯ ⇒ 1 = r m − 2 − x m ( r m − 3 − x m − 1 r m − 2 ) ⇒ 1 = r m − 2 − x m r m − 3 + x m x m − 1 r m − 2 ⇒ 1 = ( 1 + x m x m − 1 ) r m − 2 − x m r m − 3 r m − 4 = r m − 3 x m − 2 + r m − 2 ⇒ r m − 2 = r m − 4 − r m − 3 x m − 2 ⋯ ⇒ 1 = ( 1 + x m x m − 1 ) ( r m − 4 − r m − 3 x m − 2 ) − x m r m − 3 ⇒ 1 = ( 1 + x m x m − 1 ) r m − 4 − ( x m − 2 x m − 1 x m + x m − 2 + x m ) r m − 3 r_{m-3}=r_{m-2}x_{m-1}+r_{m-1}\Rightarrow r_{m-1}=r_{m-3}-r_{m-2}x_{m-1}\\
\cdots\Rightarrow 1=r_{m-2}-x_m(r_{m-3}-x_{m-1}r_{m-2})\Rightarrow 1=r_{m-2}-x_mr_{m-3}+x_mx_{m-1}r_{m-2}\Rightarrow 1=(1+x_mx_{m-1})r_{m-2}-x_mr_{m-3}\\
r_{m-4}=r_{m-3}x_{m-2}+r_{m-2}\Rightarrow r_{m-2}=r_{m-4}-r_{m-3}x_{m-2}\\
\cdots\Rightarrow1=(1+x_mx_{m-1})(r_{m-4}-r_{m-3}x_{m-2})-x_mr_{m-3}\Rightarrow 1=(1+x_mx_{m-1})r_{m-4}-(x_{m-2}x_{m-1}x_m+x_{m-2}+x_m)r_{m-3}
r m − 3 = r m − 2 x m − 1 + r m − 1 ⇒ r m − 1 = r m − 3 − r m − 2 x m − 1 ⋯ ⇒ 1 = r m − 2 − x m ( r m − 3 − x m − 1 r m − 2 ) ⇒ 1 = r m − 2 − x m r m − 3 + x m x m − 1 r m − 2 ⇒ 1 = ( 1 + x m x m − 1 ) r m − 2 − x m r m − 3 r m − 4 = r m − 3 x m − 2 + r m − 2 ⇒ r m − 2 = r m − 4 − r m − 3 x m − 2 ⋯ ⇒ 1 = ( 1 + x m x m − 1 ) ( r m − 4 − r m − 3 x m − 2 ) − x m r m − 3 ⇒ 1 = ( 1 + x m x m − 1 ) r m − 4 − ( x m − 2 x m − 1 x m + x m − 2 + x m ) r m − 3
可以通过模拟发现，总有系数可以满足等式左边为 1 1 1 r r r a , b a,b a , b a x + b y = 1 ax+by=1 a x + b y = 1
证毕。
显然 a 1 x + b 1 y = 1 a_1x+b_1y=1 a 1 x + b 1 y = 1 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) a x + b y = g cd( a , b )
由于 gcd ( a , b ) = gcd ( a , − b ) \gcd(a,b)=\gcd(a,-b) g cd( a , b ) = g cd( a , − b ) gcd \gcd g cd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int gcd (int a,int b) if (a==0 )return b; return gcd (b%a,a); } int a[100001 ];int main () ios::sync_with_stdio (false ); int n; cin>>n; for (int i=1 ;i<=n;i++){ cin>>a[i]; a[i]=abs (a[i]); } for (int i=2 ;i<=n;i++)a[i]=gcd (a[i],a[i-1 ]); cout<<a[n]; return 0 ; }
根据裴蜀定理可得，当 gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 x , y x,y x , y a x + b y = 1 ax+by=1 a x + b y = 1 能跳到所有位置上。
然而题中要求最小。
考虑 dp，列出 dp 方程式：
f gcd ( x , y ) = min ( f gcd ( x , y ) , f x + c y ) f_{\gcd(x,y)}=\min(f_{\gcd(x,y)},f_x+c_y)
f g c d ( x , y ) = min ( f g c d ( x , y ) , f x + c y )
使用 unordered_map 记录之前的状态，对于每个点进行转移即可。
时间复杂度 O ( 玄学 ) O(玄学) O ( 玄 学 )
咳咳，我之前写树上莫队的时候什么也没说。
但是很神奇的是用 unordered_map 会 WA，所以有点离谱。
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 #include <bits/stdc++.h> using namespace std;int gcd (int a,int b) if (!b)return a; return gcd (b,a%b); } int n,l[301 ],c[303 ];map<int ,int > mp; int main () ios::sync_with_stdio (false ); cin>>n; for (int i=1 ;i<=n;i++)cin>>l[i]; for (int i=1 ;i<=n;i++)cin>>c[i]; for (int i=1 ;i<=n;i++){ for (pair<int ,int > x:mp){ int _next=gcd (x.first,l[i]); if (!mp[_next])mp[_next]=c[i]+x.second; else mp[_next]=min (mp[_next],c[i]+x.second); } if (!mp[l[i]])mp[l[i]]=c[i]; else mp[l[i]]=min (mp[l[i]],c[i]); } if (!mp[1 ])mp[1 ]=-1 ; cout<<mp[1 ]; return 0 ; }
进一步结论
对于不定方程 a x + b y = n ax+by=n a x + b y = n n n n a , b a,b a , b
记 C = a b − a − b C=ab-a-b C = a b − a − b C = ( a − 1 ) ( b − 1 ) − 1 C=(a-1)(b-1)-1 C = ( a − 1 ) ( b − 1 ) − 1 a , b a,b a , b C C C
那么则有结论，对于任意整数 n n n n n n C − n C-n C − n a , b a,b a , b 。
注意此处的 x , y x,y x , y 0 0 0 C C C C C C
证明分三步：
令原方程解为：
{ x = x 0 + b t y = y 0 − a t \begin{cases}
x=x_0+bt \cr
y=y_0-at
\end{cases}
{ x = x 0 + b t y = y 0 − a t
如果控制 t t t y y y 0 0 0 a − 1 a-1 a − 1 [ 0 , C ] [0,C] [ 0 , C ] y y y a − 1 a-1 a − 1
第一步：证明当 n > C n>C n > C n n n
考虑 y m a x = a − 1 y_{max}=a-1 y m a x = a − 1
a x = n − b y > a b − a − b − b y ≥ a b − a − b − b ( a − 1 ) = − a ⇒ x > − 1 ax=n-by>ab-a-b-by\geq ab-a-b-b(a-1)=-a\Rightarrow x>-1
a x = n − b y > a b − a − b − b y ≥ a b − a − b − b ( a − 1 ) = − a ⇒ x > − 1
可见 x x x
第二步：证明 n = C n=C n = C n n n
考虑如果 n = C n=C n = C a x + b y = a b − a − b ax+by=ab-a-b a x + b y = a b − a − b
则有 a b = a ( x + 1 ) + b ( y + 1 ) ⇒ a ( b − x − 1 ) = b ( y + 1 ) ab=a(x+1)+b(y+1)\Rightarrow a(b-x-1)=b(y+1) a b = a ( x + 1 ) + b ( y + 1 ) ⇒ a ( b − x − 1 ) = b ( y + 1 )
由于 a , b a,b a , b b − x − 1 = k b , y + 1 = k a b-x-1=kb\ ,\ y+1=ka b − x − 1 = k b , y + 1 = k a
由于 y ∈ [ 0 , a − 1 ] y\in[0,a-1] y ∈ [ 0 , a − 1 ] k = 1 k=1 k = 1 x = − 1 x=-1 x = − 1 C C C
此处的证明是作者口胡的，所以与 OI Wiki 上的解释不同。
第三步：证明当 n n n C − n C-n C − n
由于 n n n y ∈ [ 0 , a − 1 ] y\in[0,a-1] y ∈ [ 0 , a − 1 ] x x x
C − n = a b − a − b − a x − b y = a ( − 1 − x ) + b ( a − 1 − y ) C-n=ab-a-b-ax-by=a(-1-x)+b(a-1-y)
C − n = a b − a − b − a x − b y = a ( − 1 − x ) + b ( a − 1 − y )
显然 − 1 − x -1-x − 1 − x a − 1 − y a-1-y a − 1 − y
证毕。
几何意义看不懂。
另一种解释
考虑模 b b b gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 0 , a , 2 a , ⋯ , ( b − 1 ) a 0,a,2a,\cdots,(b-1)a 0 , a , 2 a , ⋯ , ( b − 1 ) a b b b
那么小于等于 n n n 数量 为：
∑ i = 0 ⌊ n a ⌋ ⌊ n − a i b ⌋ \sum_{i=0}^{\left\lfloor \frac{n}{a} \right\rfloor}\left\lfloor\frac{n-ai}{b}\right\rfloor
i = 0 ∑ ⌊ a n ⌋ ⌊ b n − a i ⌋
因为对于所有剩余系的意义不同，所以要将所有剩余系的贡献累加。
用类欧几里得算法可以做到 O ( log ( max ( a , b ) ) ) O(\log(\max(a,b))) O ( log ( max ( a , b ) ) )
exgcd
这个东西主要是来求不定方程 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) a x + b y = g cd( a , b )
构造过程
考虑证明裴蜀定理的时候，对于 gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1
有了计算机，那么我们可以反带 gcd ( a , b ) ≠ 1 \gcd(a,b)\ne 1 g cd( a , b ) = 1 gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1
下面就是推式子环节了。
首先，对于欧几里得算法退出时，它的返回条件是 b = 0 b=0 b = 0
{ x = 1 y = 0 \begin{cases}x=1\cr y=0\end{cases}
{ x = 1 y = 0
然后对于任意 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) a x + b y = g cd( a , b )
a x + b y = gcd ( a , b ) = gcd ( b , a m o d b ) = b x 0 + ( a m o d b ) y 0 ⇒ a x + b y = b x 0 + ( a − ⌊ a b ⌋ × b ) y 0 = a y 0 + b ( x 0 − ⌊ a b ⌋ y 0 ) ax+by=\gcd(a,b)=\gcd(b,a \bmod b)=bx_0+(a\bmod b)y_0\\
\Rightarrow ax+by=bx_0+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)y_0=ay_0+b(x_0-\left\lfloor\frac{a}{b}\right\rfloor y_0)
a x + b y = g cd( a , b ) = g cd( b , a m o d b ) = b x 0 + ( a m o d b ) y 0 ⇒ a x + b y = b x 0 + ( a − ⌊ b a ⌋ × b ) y 0 = a y 0 + b ( x 0 − ⌊ b a ⌋ y 0 )
所以推出一组可行的解 x = y 0 , y = x 0 − ⌊ a b ⌋ y 0 x=y_0\ ,\ y=x_0-\left\lfloor\frac{a}{b}\right\rfloor y_0 x = y 0 , y = x 0 − ⌊ b a ⌋ y 0
递推即可。
这题要求是真的多。
首先用 exgcd 算出一组特解，然后来考虑各组解的关系。
列出式子 a ( x + p ) + b ( y − q ) = a x + b y = c a(x+p)+b(y-q)=ax+by=c a ( x + p ) + b ( y − q ) = a x + b y = c a p = b q ap=bq a p = b q
由于 p p p q q q p m i n = 1 a × lcm ( a , b ) p_{min}=\frac{1}{a}\times\operatorname{lcm}(a,b) p m i n = a 1 × l c m ( a , b ) q m i n q_{min} q m i n
然后就可以直接算出题中要求的所有信息了。
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 #include <bits/stdc++.h> using namespace std;#define int long long int x,y,_a,_b,_c;int exgcd (int a,int b) int d=a; if (b==0 )x=1 ,y=0 ; else d=exgcd (b,a%b),swap (x,y),y-=a/b*x; return d; } signed main () ios::sync_with_stdio (0 ); int n; cin>>n; while (n--){ cin>>_a>>_b>>_c; int d=exgcd (_a,_b); if (_c%d){ cout<<-1 <<"\n" ; continue ; } int k=_c/d; x*=k,y*=k; int p=_b/d,q=_a/d; int test=y/q; int tx=test*p+x,ty=-test*q+y; if (ty<=0 )ty+=q,tx-=p; if (tx<=0 ){ cout<<-(tx/p)*p+p+tx<<" " <<ty<<"\n" ; } else { cout<<(tx-1 )/p+1 <<" " <<(tx-1 )%p+1 <<" " <<ty<<" " <<tx<<" " <<(tx-1 )/p*q+ty<<"\n" ; } } return 0 ; }
考虑把这道题的参数转换成 a x + b y = n ax+by=n a x + b y = n
考虑追及问题，所以可以列出：Δ v x + L y = Δ s \Delta vx+Ly=\Delta s Δ v x + L y = Δ s
算出特解之后像上面那道题一样算 x x x
注意 Δ v \Delta v Δ v Δ s \Delta s Δ s
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 #include <bits/stdc++.h> using namespace std;#define int long long int n,m,x,y,L;int _x,_y;int exgcd (int a,int b) int d=a; if (!b)_x=1 ,_y=0 ; else d=exgcd (b,a%b),swap (_x,_y),_y-=a/b*_x; return d; } signed main () ios::sync_with_stdio (0 ); cin>>x>>y>>m>>n>>L; int z=n-m,f=x-y; if (z<0 )z=-z,f=-f; if (f==0 ){ cout<<0 ; return 0 ; } int k=exgcd (z,L),p=L/k,q=z/k; _x*=(f/k),_y*=(f/k); if (f%k){ cout<<"Impossible" ; } else { if (_x>0 )cout<<(_x-1 )%p+1 ; else cout<<_x%p+p; } return 0 ; }
水题。
考虑式子 a x ≡ 1 ( m o d b ) ax \equiv 1\pmod b a x ≡ 1 ( m o d b ) a x − b y = 1 ax-by=1 a x − b y = 1 x x x
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;int x,y;int exgcd (int a,int b) int d=a; if (!b)x=1 ,y=0 ; else d=exgcd (b,a%b),swap (x,y),y-=a/b*x; return d; } int main () ios::sync_with_stdio (0 ); int n,m; cin>>n>>m; int d=exgcd (n,m); y=-y; int p=m/d,ans; if (x>0 )ans=(x-1 )%p+1 ; else ans=x%p+p; cout<<ans; return 0 ; }
较复杂的一道题。
判断每个野人生存周期以内的两两的 exgcd 即可。
然后由于没有单调性不能二分，直接枚举就行了。
和 P1516 差不多。
时间复杂度 O ( M n 2 log c ) O(Mn^2\log c) O ( M n 2 log c )
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 #include <bits/stdc++.h> using namespace std;int x,y;int exgcd (int a,int b) int d=a; if (!b)x=1 ,y=0 ; else d=exgcd (b,a%b),swap (x,y),y-=a/b*x; return d; } int c[21 ],p[21 ],l[21 ],n;bool check (int L) for (int i=1 ;i<=n;i++){ for (int j=1 ;j<i;j++){ int z=p[j]-p[i],f=c[i]-c[j]; if (z<0 )z=-z,f=-f; if (f==0 )return 0 ; int d=exgcd (z,L); if (f%d)continue ; int p=L/d,q=z/d; x*=(f/d),y*=(f/d); int ans; if (x>0 )ans=(x-1 )%p+1 ; else ans=x%p+p; if (ans<=l[i]&&ans<=l[j])return 0 ; } } return 1 ; } int maxc=-1 ;int main () ios::sync_with_stdio (0 ); cin>>n; for (int i=1 ;i<=n;i++)cin>>c[i]>>p[i]>>l[i],maxc=max (c[i],maxc); for (;;maxc++)if (check (maxc)){ cout<<maxc; return 0 ; } return 0 ; }
枚举每个 C C C exgcd ( A , B ) \operatorname{exgcd}(A,B) e x g c d ( A , B ) A x + B y = P − i C Ax+By=P-iC A x + B y = P − i C
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 42 43 #include <bits/stdc++.h> using namespace std;#define int long long int T,a,b,c,p,x,y;int exgcd (int a,int b) int d=a; if (!b)x=1 ,y=0 ; else d=exgcd (b,a%b),swap (x,y),y-=a/b*x; return d; } signed main () ios::sync_with_stdio (0 ); cin>>T; int Y=T; while (T--){ int ans=0 ; cin>>a>>b>>c>>p; int d=exgcd (a,b); for (int i=0 ;i*c<=p;i++){ if ((p-i*c)%d)continue ; int tx=x*(p-i*c)/d,ty=y*(p-i*c)/d; int p=b/d,q=a/d; int res=0 ; if (tx>=0 ||tx%p==0 )res=tx%p; else res=tx%p+p; res=(res-tx)/p; ty-=res*q; if (ty>=0 )ans+=ty/q+1 ; } cout<<"Case " <<Y-T<<": " <<ans<<"\n" ; } return 0 ; }
不会证明这个结论，因此直接搬 tj 了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;int x,y;int exgcd (int a,int b) int d=a; if (!b)x=1 ,y=0 ; else d=exgcd (b,a%b),swap (x,y),y-=a/b*x; return d; } int main () ios::sync_with_stdio (0 ); int a,b,gcd; while (cin>>a>>b)gcd=exgcd (a,b),cout<<x<<" " <<y<<" " <<gcd<<"\n" ; return 0 ; }
类欧几里得算法
这个算法是用来在 O ( log n ) O(\log n) O ( log n )
f ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ g ( a , b , c , n ) = ∑ i = 0 n i ⌊ a i + b c ⌋ h ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ 2 f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\
g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor\\
h(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2
f ( a , b , c , n ) = i = 0 ∑ n ⌊ c a i + b ⌋ g ( a , b , c , n ) = i = 0 ∑ n i ⌊ c a i + b ⌋ h ( a , b , c , n ) = i = 0 ∑ n ⌊ c a i + b ⌋ 2
推式子
然后开始艰难地推式子…
先令 s 0 ( n ) = n + 1 , s 1 ( n ) = ( n + 1 ) n 2 , s 2 ( n ) = n ( n + 1 ) ( 2 n + 1 ) 6 s^0(n)=n+1\ ,\ s^1(n)=\frac{(n+1)n}{2}\ ,\ s^2(n)=\frac{n(n+1)(2n+1)}{6} s 0 ( n ) = n + 1 , s 1 ( n ) = 2 ( n + 1 ) n , s 2 ( n ) = 6 n ( n + 1 ) ( 2 n + 1 )
对于 a>c \or b>c 的情况：
f ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ = ∑ i = 0 n ( ⌊ ( a m o d c ) i + b m o d c c ⌋ + ⌊ a c ⌋ i + ⌊ b c ⌋ ) = ⌊ b c ⌋ × s 0 ( n ) + ⌊ a c ⌋ × s 1 ( n ) + f ( a m o d c , b m o d c , c , n ) g ( a , b , c , n ) = ∑ i = 0 n i ⌊ a i + b c ⌋ = ∑ i = 0 n i ( ⌊ ( a m o d c ) i + b m o d c c ⌋ + ⌊ a c ⌋ i + ⌊ b c ⌋ ) = ∑ i = 0 n ( ⌊ a c ⌋ i 2 + ⌊ b c ⌋ i ) + g ( a m o d c , b m o d c , c , n ) = ⌊ a c ⌋ × s 2 ( n ) + ⌊ b c ⌋ × s 1 ( n ) + g ( a m o d c , b m o d c , c , n ) h ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ 2 = ∑ i = 0 n ( ⌊ ( a m o d c ) i + b m o d c c ⌋ + ⌊ a c ⌋ i + ⌊ b c ⌋ ) 2 = h ( a m o d c , b m o d c , c , n ) + 2 ⌊ a c ⌋ g ( a m o d c , b m o d c , c , n ) + 2 ⌊ b c ⌋ f ( a m o d c , b m o d c , c , n ) + ∑ i = 0 n ( ⌊ a c ⌋ 2 i 2 + ⌊ b c ⌋ 2 + 2 ⌊ a c ⌋ ⌊ b c ⌋ i ) = s 0 ( n ) × ⌊ b c ⌋ 2 + s 1 ( n ) × 2 ⌊ a c ⌋ ⌊ b c ⌋ + s 2 ( n ) × ⌊ a c ⌋ 2 + h ( a m o d c , b m o d c , c , n ) + 2 ⌊ a c ⌋ g ( a m o d c , b m o d c , c , n ) + 2 ⌊ b c ⌋ f ( a m o d c , b m o d c , c , n ) \begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\cr
&=\sum_{i=0}^n\left(\left\lfloor\frac{(a\bmod c)i+b\bmod c}{c}\right\rfloor+\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right)\cr
&=\left\lfloor\frac{b}{c}\right\rfloor\times s^0(n)+\left\lfloor\frac{a}{c}\right\rfloor \times s^1(n)+f(a\bmod c,b\bmod c,c,n)\cr
g(a,b,c,n)&=\sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor\cr
&=\sum_{i=0}^ni\left(\left\lfloor\frac{(a\bmod c)i+b\bmod c}{c}\right\rfloor+\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right)\cr
&=\sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i^2+\left\lfloor\frac{b}{c}\right\rfloor i\right)+g(a\bmod c,b\bmod c,c,n)\cr
&=\left\lfloor\frac{a}{c}\right\rfloor\times s^2(n)+\left\lfloor\frac{b}{c}\right\rfloor\times s^1(n)+g(a\bmod c,b\bmod c,c,n)\cr
h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\cr
&=\sum_{i=0}^n\left(\left\lfloor\frac{(a\bmod c)i+b\bmod c}{c}\right\rfloor+\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right)^2\cr
&=h(a\bmod c,b\bmod c,c,n)+2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)+\sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor^2 i^2+\left\lfloor\frac{b}{c}\right\rfloor^2+2\left\lfloor\frac{a}{c}\right\rfloor \left\lfloor\frac{b}{c}\right\rfloor i\right)\cr
&=s^0(n)\times \left\lfloor\frac{b}{c}\right\rfloor^2+s^1(n)\times 2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor+s^2(n)\times \left\lfloor\frac{a}{c}\right\rfloor^2+h(a\bmod c,b\bmod c,c,n)+2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)
\end{aligned}
f ( a , b , c , n ) g ( a , b , c , n ) h ( a , b , c , n ) = i = 0 ∑ n ⌊ c a i + b ⌋ = i = 0 ∑ n ( ⌊ c ( a m o d c ) i + b m o d c ⌋ + ⌊ c a ⌋ i + ⌊ c b ⌋ ) = ⌊ c b ⌋ × s 0 ( n ) + ⌊ c a ⌋ × s 1 ( n ) + f ( a m o d c , b m o d c , c , n ) = i = 0 ∑ n i ⌊ c a i + b ⌋ = i = 0 ∑ n i ( ⌊ c ( a m o d c ) i + b m o d c ⌋ + ⌊ c a ⌋ i + ⌊ c b ⌋ ) = i = 0 ∑ n ( ⌊ c a ⌋ i 2 + ⌊ c b ⌋ i ) + g ( a m o d c , b m o d c , c , n ) = ⌊ c a ⌋ × s 2 ( n ) + ⌊ c b ⌋ × s 1 ( n ) + g ( a m o d c , b m o d c , c , n ) = i = 0 ∑ n ⌊ c a i + b ⌋ 2 = i = 0 ∑ n ( ⌊ c ( a m o d c ) i + b m o d c ⌋ + ⌊ c a ⌋ i + ⌊ c b ⌋ ) 2 = h ( a m o d c , b m o d c , c , n ) + 2 ⌊ c a ⌋ g ( a m o d c , b m o d c , c , n ) + 2 ⌊ c b ⌋ f ( a m o d c , b m o d c , c , n ) + i = 0 ∑ n ( ⌊ c a ⌋ 2 i 2 + ⌊ c b ⌋ 2 + 2 ⌊ c a ⌋ ⌊ c b ⌋ i ) = s 0 ( n ) × ⌊ c b ⌋ 2 + s 1 ( n ) × 2 ⌊ c a ⌋ ⌊ c b ⌋ + s 2 ( n ) × ⌊ c a ⌋ 2 + h ( a m o d c , b m o d c , c , n ) + 2 ⌊ c a ⌋ g ( a m o d c , b m o d c , c , n ) + 2 ⌊ c b ⌋ f ( a m o d c , b m o d c , c , n )
作者的手已经打废了。/kk
对于 a<c\and b<c 的情况：
先看三个式子同样要用到的东西：
令 m = ⌊ a n + b c ⌋ \displaystyle m=\left\lfloor\frac{an+b}{c}\right\rfloor m = ⌊ c a n + b ⌋
∑ i = 0 n [ j < ⌊ a i + b c ⌋ ] = ∑ i = 0 n [ j + 1 ≤ a i + b c ] = ∑ i = 0 n [ j c + c ≤ a i + b ] = ∑ i = 0 n [ a i ≥ j c + c − b ] = ∑ i = 0 n [ a i > j c + c − b − 1 ] = ∑ i = 0 n [ i > ⌊ j c + c + b − 1 a ⌋ ] = n − ⌊ j c + c + b − 1 a ⌋ \begin{aligned}
\sum_{i=0}^n\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]&=\sum_{i=0}^n\left[j+1\leq\frac{ai+b}{c}\right]\cr
&=\sum_{i=0}^{n}\left[jc+c\leq ai+b\right]\cr
&=\sum_{i=0}^{n}[ai\geq jc+c-b]\cr
&=\sum_{i=0}^n[ai>jc+c-b-1]\cr
&=\sum_{i=0}^n\left[i>\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right]\cr
&=n-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor
\end{aligned}
i = 0 ∑ n [ j < ⌊ c a i + b ⌋ ] = i = 0 ∑ n [ j + 1 ≤ c a i + b ] = i = 0 ∑ n [ j c + c ≤ a i + b ] = i = 0 ∑ n [ a i ≥ j c + c − b ] = i = 0 ∑ n [ a i > j c + c − b − 1 ] = i = 0 ∑ n [ i > ⌊ a j c + c + b − 1 ⌋ ] = n − ⌊ a j c + c + b − 1 ⌋
然后逐个击破：
f ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ = ∑ i = 0 n ∑ j = 0 ⌊ a i + b c ⌋ − 1 1 = ∑ i = 0 n ∑ j = 0 m − 1 [ j < ⌊ a i + b c ⌋ ] = ∑ j = 0 m − 1 ∑ i = 0 n [ j < ⌊ a i + b c ⌋ ] = ∑ j = 0 m − 1 ( n − ⌊ j c + c + b − 1 a ⌋ ) = n m − f ( c , c − b − 1 , a , m − 1 ) g ( a , b , c , n ) = ∑ i = 0 n i ⌊ a i + b c ⌋ = ∑ i = 0 n ∑ j = 0 ⌊ a i + b c ⌋ − 1 i = ∑ i = 0 n ∑ j = 0 m − 1 ( [ j < ⌊ a i + b c ⌋ ] × i ) = ∑ j = 0 m − 1 ∑ i = 0 n ( [ j < ⌊ a i + b c ⌋ ] × i ) = ∑ j = 0 m − 1 ∑ i = 0 n ( [ i > ⌊ j c + c + b − 1 a ⌋ ] × i ) = ∑ j = 0 m − 1 ( n + ⌊ j c + c + b − 1 a ⌋ + 1 ) × ( n − ⌊ j c + c + b − 1 a ⌋ ) 2 = ∑ j = 0 m − 1 ( n 2 − ⌊ j c + c + b − 1 a ⌋ 2 + n − ⌊ j c + c + b − 1 a ⌋ ) 2 = n ( n + 1 ) m − h ( c , c − b − 1 , a , m − 1 ) − f ( c , c − b − 1 , a , m − 1 ) 2 h ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ 2 = 2 ∑ i = 0 n ∑ j = 0 ⌊ a i + b c ⌋ − 1 ( j + 1 ) − ∑ i = 0 n ⌊ a i + b c ⌋ = 2 ∑ i = 0 n ∑ j = 0 m − 1 ( [ j < ⌊ a i + b c ⌋ ] × ( j + 1 ) ) − f ( a , b , c , n ) = 2 ∑ j = 0 m − 1 ( j + 1 ) ∑ i = 0 n [ j < ⌊ a i + b c ⌋ ] − f ( a , b , c , n ) = 2 ∑ j = 0 m − 1 ( ( j + 1 ) × ( n − ⌊ j c + c + b − 1 a ⌋ ) ) − f ( a , b , c , n ) = ( m + 1 ) m n − 2 ∑ j = 0 m − 1 ( j ⌊ j c + c + b − 1 a ⌋ + ⌊ j c + c + b − 1 a ⌋ ) − f ( a , b , c , n ) = ( m + 1 ) m n − 2 g ( c , c − b − 1 , a , m − 1 ) − 2 f ( c , c − b − 1 , a , m − 1 ) − f ( a , b , c , n ) \begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\cr
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}1\cr
&=\sum_{i=0}^n\sum_{j=0}^{m-1}\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\cr
&=\sum_{j=0}^{m-1}\sum_{i=0}^n\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\cr
&=\sum_{j=0}^{m-1}\left(n-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right)\cr
&=nm-f(c,c-b-1,a,m-1)\cr
g(a,b,c,n)&=\sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor\cr
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}i\cr
&=\sum_{i=0}^n\sum_{j=0}^{m-1}\left(\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\times i\right)\cr
&=\sum_{j=0}^{m-1}\sum_{i=0}^n\left(\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\times i\right)\cr
&=\sum_{j=0}^{m-1}\sum_{i=0}^n\left(\left[i>\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right]\times i\right)\cr
&=\sum_{j=0}^{m-1}\frac{\left(n+\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor+1\right)\times\left(n-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right)}{2}\cr
&=\frac{\displaystyle\sum_{j=0}^{m-1}\left(n^2-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor^2+n-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right)}{2}\cr
&=\frac{n(n+1)m-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)}{2}\cr
h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\cr
&=2\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}(j+1)-\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\cr
&=2\sum_{i=0}^n\sum_{j=0}^{m-1}\left(\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\times (j+1)\right)-f(a,b,c,n)\cr
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]-f(a,b,c,n)\cr
&=2\sum_{j=0}^{m-1}\left((j+1)\times \left(n-\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right)\right)-f(a,b,c,n)\cr
&=(m+1)mn-2\sum_{j=0}^{m-1}\left(j\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor+\left\lfloor\frac{jc+c+b-1}{a}\right\rfloor\right)-f(a,b,c,n)\cr
&=(m+1)mn-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)
\end{aligned}
f ( a , b , c , n ) g ( a , b , c , n ) h ( a , b , c , n ) = i = 0 ∑ n ⌊ c a i + b ⌋ = i = 0 ∑ n j = 0 ∑ ⌊ c a i + b ⌋ − 1 1 = i = 0 ∑ n j = 0 ∑ m − 1 [ j < ⌊ c a i + b ⌋ ] = j = 0 ∑ m − 1 i = 0 ∑ n [ j < ⌊ c a i + b ⌋ ] = j = 0 ∑ m − 1 ( n − ⌊ a j c + c + b − 1 ⌋ ) = n m − f ( c , c − b − 1 , a , m − 1 ) = i = 0 ∑ n i ⌊ c a i + b ⌋ = i = 0 ∑ n j = 0 ∑ ⌊ c a i + b ⌋ − 1 i = i = 0 ∑ n j = 0 ∑ m − 1 ( [ j < ⌊ c a i + b ⌋ ] × i ) = j = 0 ∑ m − 1 i = 0 ∑ n ( [ j < ⌊ c a i + b ⌋ ] × i ) = j = 0 ∑ m − 1 i = 0 ∑ n ( [ i > ⌊ a j c + c + b − 1 ⌋ ] × i ) = j = 0 ∑ m − 1 2 ( n + ⌊ a j c + c + b − 1 ⌋ + 1 ) × ( n − ⌊ a j c + c + b − 1 ⌋ ) = 2 j = 0 ∑ m − 1 ( n 2 − ⌊ a j c + c + b − 1 ⌋ 2 + n − ⌊ a j c + c + b − 1 ⌋ ) = 2 n ( n + 1 ) m − h ( c , c − b − 1 , a , m − 1 ) − f ( c , c − b − 1 , a , m − 1 ) = i = 0 ∑ n ⌊ c a i + b ⌋ 2 = 2 i = 0 ∑ n j = 0 ∑ ⌊ c a i + b ⌋ − 1 ( j + 1 ) − i = 0 ∑ n ⌊ c a i + b ⌋ = 2 i = 0 ∑ n j = 0 ∑ m − 1 ( [ j < ⌊ c a i + b ⌋ ] × ( j + 1 ) ) − f ( a , b , c , n ) = 2 j = 0 ∑ m − 1 ( j + 1 ) i = 0 ∑ n [ j < ⌊ c a i + b ⌋ ] − f ( a , b , c , n ) = 2 j = 0 ∑ m − 1 ( ( j + 1 ) × ( n − ⌊ a j c + c + b − 1 ⌋ ) ) − f ( a , b , c , n ) = ( m + 1 ) m n − 2 j = 0 ∑ m − 1 ( j ⌊ a j c + c + b − 1 ⌋ + ⌊ a j c + c + b − 1 ⌋ ) − f ( a , b , c , n ) = ( m + 1 ) m n − 2 g ( c , c − b − 1 , a , m − 1 ) − 2 f ( c , c − b − 1 , a , m − 1 ) − f ( a , b , c , n )
边界：
f ( 0 , b , c , n ) = s 0 ( n ) × ⌊ b c ⌋ g ( 0 , b , c , n ) = s 1 ( n ) × ⌊ b c ⌋ h ( 0 , b , c , n ) = s 0 ( n ) × ⌊ b c ⌋ 2 \begin{aligned}
f(0,b,c,n)&=s^0(n)\times \left\lfloor\frac{b}{c}\right\rfloor\cr
g(0,b,c,n)&=s^1(n)\times \left\lfloor\frac{b}{c}\right\rfloor\cr
h(0,b,c,n)&=s^0(n)\times\left\lfloor\frac{b}{c}\right\rfloor^2\cr
\end{aligned}
f ( 0 , b , c , n ) g ( 0 , b , c , n ) h ( 0 , b , c , n ) = s 0 ( n ) × ⌊ c b ⌋ = s 1 ( n ) × ⌊ c b ⌋ = s 0 ( n ) × ⌊ c b ⌋ 2
写完这个东西就去复习 CSP 了。
板子题：P5170
没啥可说的，注意取模即可。
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 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> using namespace std;#define int long long const long long mod=998244353 ;struct R { int f,g,h; }ans; R getr (int _f,int _g,int _h) { R temp; temp.f=_f; temp.g=_g; temp.h=_h; return temp; } int I2=499122177 ,I6=166374059 ;int s0 (int k) return k+1 ; } int s1 (int k) return k*(k+1 )%mod*I2%mod; } int s2 (int k) return k*(k+1 )%mod*(2 *k+1 )%mod*I6%mod; } R simgcd (int a,int b,int c,int n) { int F=0 ,G=0 ,H=0 ; if (a==0 )return getr ((b/c)*s0 (n)%mod,(b/c)*s1 (n)%mod,(b/c)*(b/c)%mod*s0 (n)%mod); R res; if (a>=c||b>=c){ res=simgcd (a%c,b%c,c,n); F=res.f+b/c*s0 (n)%mod+a/c*s1 (n)%mod; G=res.g+a/c*s2 (n)%mod+b/c*s1 (n)%mod; H=b/c*2 *res.f%mod+a/c*2 *res.g%mod+res.h+b/c*(b/c)%mod*s0 (n)%mod+b/c*(a/c)*2 %mod*s1 (n)%mod+(a/c)*(a/c)%mod*s2 (n)%mod; return getr (F%mod,G%mod,H%mod); } int m=(a*n+b)/c; res=simgcd (c,c-b-1 ,a,m-1 ); F=n*m%mod-res.f%mod; G=(n*(n+1 )%mod*m%mod-res.h%mod-res.f%mod)*I2%mod; H=(m+1 )*m%mod*n%mod+-2 *res.g%mod-2 *res.f%mod-F%mod; return getr ((F%mod+mod)%mod,(G%mod+mod)%mod,(H%mod+mod)%mod); } signed main () ios::sync_with_stdio (0 ); int T,aa,bb,cc,nn; cin>>T; while (T--){ cin>>nn>>aa>>bb>>cc; ans=simgcd (aa,bb,cc,nn); cout<<(ans.f%mod)<<" " <<(ans.h%mod)<<" " <<(ans.g%mod)<<"\n" ; } return 0 ; }
应用：P5171
CSP 复习前的最后一道题。
考虑分开讨论 x , y x,y x , y
之前好像有证明 gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1
先讨论 y y y
a x + b y ≤ c ⇒ b y ≤ c − a x ⇒ y ≤ ⌊ c − a x b ⌋ ax+by\leq c\Rightarrow by\leq c-ax\Rightarrow y\leq\left\lfloor\frac{c-ax}{b}\right\rfloor
a x + b y ≤ c ⇒ b y ≤ c − a x ⇒ y ≤ ⌊ b c − a x ⌋
所以对于 y y y x x x ⌊ c − a x b ⌋ + 1 \left\lfloor\frac{c-ax}{b}\right\rfloor+1 ⌊ b c − a x ⌋ + 1
再来讨论 x x x y = 0 y=0 y = 0 x x x ⌊ c a ⌋ \lfloor\frac{c}{a}\rfloor ⌊ a c ⌋ x ∈ [ 0 , ⌊ c a ⌋ ] x\in[0,\left\lfloor\frac{c}{a}\right\rfloor] x ∈ [ 0 , ⌊ a c ⌋ ]
所以式子列出来就是：
∑ x = 0 ⌊ c a ⌋ ( ⌊ c − a x b ⌋ + 1 ) \sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left(\left\lfloor\frac{c-ax}{b}\right\rfloor+1\right)
x = 0 ∑ ⌊ a c ⌋ ( ⌊ b c − a x ⌋ + 1 )
因为 − a < 0 -a<0 − a < 0 x x x y y y a , b a,b a , b
∑ x = 0 ⌊ c a ⌋ ( ⌊ ( b − a ) x + c b ⌋ − x ) + s 0 ( ⌊ c a ⌋ ) = ∑ x = 0 ⌊ c a ⌋ ⌊ ( b − a ) x + c b ⌋ − s 1 ( ⌊ c a ⌋ ) + s 0 ( ⌊ c a ⌋ ) \sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left(\left\lfloor\frac{(b-a)x+c}{b}\right\rfloor-x\right)+s^0\left(\left\lfloor\frac{c}{a}\right\rfloor\right)=\sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor\frac{(b-a)x+c}{b}\right\rfloor-s^1\left(\left\lfloor\frac{c}{a}\right\rfloor\right)+s^0\left(\left\lfloor\frac{c}{a}\right\rfloor\right)
x = 0 ∑ ⌊ a c ⌋ ( ⌊ b ( b − a ) x + c ⌋ − x ) + s 0 ( ⌊ a c ⌋ ) = x = 0 ∑ ⌊ a c ⌋ ⌊ b ( b − a ) x + c ⌋ − s 1 ( ⌊ a c ⌋ ) + s 0 ( ⌊ a c ⌋ )
然后就可以求解了。
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 #include <bits/stdc++.h> using namespace std;#define int long long int s0 (int k) return k+1 ; } int s1 (int k) return k*(k+1 )/2 ; } int simgcd (int a,int b,int c,int n) int res=0 ; if (a>=c||b>=c)res+=s1 (n)*(a/c)+s0 (n)*(b/c),a%=c,b%=c; if (a==0 )return s0 (n)*(b/c)+res; int m=(a*n+b)/c; return m*n-simgcd (c,c-b-1 ,a,m-1 )+res; } signed main () ios::sync_with_stdio (0 ); int A,B,C; cin>>A>>B>>C; if (A>B)swap (A,B); int ans=simgcd (B-A,C,B,C/A); ans-=s1 (C/A)-C/A; cout<<ans+1 ; return 0 ; }
鸽
这里应该还有 3 3 3
没写的：AT_abc283_h，P5172，P5179。
