传送门：loj138
题解
被标题坑进去，断断续续做了一天。。。确实是“类欧几里得算法”啊。。。
原题解-fjzzq2002
设答案为函数f(a,b,c,n,k1,k2)=i=0∑nik1⌊cai+b⌋k2
考虑以下情况：
-
⌊cai+b⌋为常量(a=0或⌊can+b⌋=0)，直接拉格朗日插值算出i=0∑nik1即可。
-
a≥c或b≥c，f(a,b,c,n,k1,k2)=i=0∑nik1(⌊ca⌋⋅i+⌊cb⌋+⌊ci⋅(a%c)+b%c⌋)k2，二项式展开一下得到若干λi=0∑nik1(⌊ci⋅(a%c)+b%c⌋)k2，迭代求解f(a%c,b%c,n,k1,k2)即可。
-
不满足上面两种情况(a<c,b<c)，把ik2转成j=0∑i−1(j+1)k2−jk2(设0k2=0)。
设m=⌊can+b⌋>0，则
f(a,b,c,n,k1,k2)
=t=0∑m−1((t+1)k2−tk2)i=0∑nik1[⌊cai+b⌋≥t+1]
=t=0∑m−1((t+1)k2−
