水题（初等数论相关）

水题（初等数论相关）

给你 3 个正整数 n,a,b，求(sum_{i=0}^n lfloor frac{a^i}{b} floor)的值。由于答案可能会很大，所以你只需要求出答案关于353448299取模的值。对于30%的数据，n<=1e5，a<=1e18，b<=1e8。对于20%的数据，n<=1e18，a=b-1，b<=1e18。对于剩下50%的数据，n<=1e18，a<=1e18，b<=1e5。有T<=100组数据。

我好sb啊。。由于同余中除法运算必须要用逆元，因此对于下取整这种东西并玩不来。考虑拆分式子，显然([frac{a^i}{b}]=frac{a^i}{b}-frac{a^i\%b}{b})。第一个部分显然可以用等比数列求和来解决，后面那个部分可以(O(n))爆算，这样就避开了下取整，而能在(O(tn))的时间复杂度内算出式子。

但是这个算法对于n<=1e8的情况依然力不从心。我们先来看a=b-1的数据点，可以发现(a^i\%b)的值要么是1要么是b-1（因为((b-1)^2=b^2+2b+1)）。剩下的就是用公式了。

还有剩下30%，是b<=1e5的数据。由于(a^i\%b)会有一个长度小于b的循环节（不一定从第一个数开始循环！），找到这个循环就可以了。

结合这三个算法，就可以拿到满分了。至于程序。。真的没希望的。