P16098 [ICPC 2019 NAIPC] It‘ s a Mod, Mod, Mod, Mod World 题解

P16098 [ICPC 2019 NAIPC] It’ s a Mod, Mod, Mod, Mod WorldLink: https://www.luogu.com.cn/problem/P16098题目描述给定多个测试用例每个测试用例包含三个整数p pp、q qq和n nn。求∑ i 1 n [ ( p ⋅ i ) m o d q ] \sum_{i1}^{n} [(p \cdot i) \bmod q]∑i1n​[(p⋅i)modq]即p pp的前n nn个倍数分别对q qq取模后的和。注意总和不需要取模。输入格式每个输入的第一行包含一个整数W WW1 ≤ W ≤ 10 5 1 \leq W \leq 10^51≤W≤105表示你需要解决的测试用例个数。接下来的W WW行每行包含三个空格分隔的整数p pp、q qq和n nn1 ≤ p , q , n ≤ 10 6 1 \leq p, q, n \leq 10^61≤p,q,n≤106即上述问题中的参数。输出格式输出W WW行每行一个整数表示对应测试用例的答案按输入顺序输出。输入输出样例 #1输入 #13 2 7 2 1 4 5 3 8 10输出 #16 7 37Solution1. 题意输入n , p , q n,p,qn,p,q三个整数求出表达式A ∑ i 1 n ( ( p ⋅ i ) m o d q ) A \sum_{i1}^n \Big((p\cdot i) \bmod q\Big)Ai1∑n​((p⋅i)modq)的值。2. 分析根据求余的基本定义x m o d q x − q ⋅ ⌊ x q ⌋ x \bmod q x - q \cdot \left \lfloor \dfrac{x}{q} \right \rfloorxmodqx−q⋅⌊qx​⌋因此可以考虑把这个式子拆开A ∑ i 1 n ( p ⋅ i ) − q ⋅ ∑ i 1 n ⌊ p ⋅ i q ⌋ p n ( n 1 ) 2 − q ⋅ ∑ i 1 n ⌊ p ⋅ i q ⌋ A \sum_{i1}^n (p\cdot i) - q\cdot \sum_{i1}^n \left \lfloor \dfrac{p \cdot i}{q} \right \rfloor \dfrac{pn(n1)}{2} - q \cdot \sum_{i1}^n \left \lfloor \dfrac{p \cdot i}{q} \right \rfloorAi1∑n​(p⋅i)−q⋅i1∑n​⌊qp⋅i​⌋2pn(n1)​−q⋅i1∑n​⌊qp⋅i​⌋前半部分直接O ( 1 ) O(1)O(1)时间复杂度求得后半部分的这一系列向下取整的求和属于类欧几里得算法的变体。若设a , b , c , n a,b,c,na,b,c,n为自然数且c ≠ 0 c \ne 0c0函数f ( a , b , c , n ) ∑ i 1 n ⌊ a ⋅ i b c ⌋ f(a,b,c,n) \sum_{i1}^n \left \lfloor \dfrac{a \cdot i b}{c} \right \rfloorf(a,b,c,n)i1∑n​⌊ca⋅ib​⌋则数学上可以证明存在关系f ( a , b , c , n ) { 0 , n ≤ 0 n ⋅ ⌊ a n b c ⌋ − f ( c , c − b − 1 , a , ⌊ a n b c ⌋ − 1 ) , n ≥ 1 f(a,b,c,n) \begin{cases} 0 , n \le 0 \\ n \cdot \left \lfloor \dfrac{an b}{c} \right \rfloor - f\left(c,c-b-1,a,\left \lfloor \dfrac{an b}{c} \right \rfloor - 1\right) , n \ge 1 \end{cases}f(a,b,c,n)⎩⎨⎧​0n⋅⌊canb​⌋−f(c,c−b−1,a,⌊canb​⌋−1)​,n≤0,n≥1​成立 [1]。这是一个递归函数照着这个表达式即可在O ( log ⁡ ( min ⁡ ( a , c , n ) ) ) O(\log(\min(a,c,n)))O(log(min(a,c,n)))的时间复杂度计算出f ff。类似于所有其他的递归算法比如斐波那契数列、搜索求f ff也可以写出非递归版本。3. 代码递归版本usingSystem;classP16098_1{publicstaticlongFloorSum(longa,longb0,longc1,longn1){if(ac||bc){returnFloorSum(a%c,b%c,c,n)a/c*n*(n1)/2b/c*(n1);}longm(a*nb)/c;if(m0){return0;}else{returnm*n-FloorSum(c,c-b-1,a,m-1);}}publicstaticvoidSolve(){varinputConsole.ReadLine().Split();intpConvert.ToInt32(input[0]);intqConvert.ToInt32(input[1]);intnConvert.ToInt32(input[2]);Console.WriteLine(p*n*(n1)/2-q*FloorSum(p,0,q,n));}staticvoidMain(){inttConvert.ToInt32(Console.ReadLine());for(inti0;it;i){Solve();}}}非递归版本usingSystem;classP16098_2{publicstaticlongFloorSum(longn,longm,longa,longb0)// sum of floor((a * ib)/m) for i0 to n-1{longresult0;while(true){if(am){result(n-1)*n/2*(a/m);a%m;}if(bm){resultn*(b/m);b%m;}longy_maxa*nb;if(y_maxm){returnresult;}ny_max/m;by_max%m;(m,a)(a,m);}}publicstaticvoidSolve(){varinputConsole.ReadLine().Split();longpConvert.ToInt32(input[0]);longqConvert.ToInt32(input[1]);longnConvert.ToInt32(input[2]);Console.WriteLine(-q*FloorSum(n1,q,p)p*n*(n1)/2);}staticvoidMain(){inttConvert.ToInt32(Console.ReadLine());for(inti0;it;i){Solve();}}}