Suhana and Equation | codechef 几何级数的模和

2019-04-14 16:23发布

站内文章 / 模拟电子
18066 0 1613
Suhana and Equation
 f(N) = 00 + 11 + 22 + 33 + 44 + ... + NN    求模m的和。N很大，1e9级别，m不是很大，也就几十万。限时1s. 先利用取模的性质：(i + m * k) % m = i % m。对f(N)进行等价划分： i ^ i + (i + m) ^ (i +m) + (i +2*m) ^ (i + 2*m) + ... = i ^ i + i ^ (i + m) + i ^ (i + 2*m) + ... 等式右边提出一个 a1 = i ^ i. 令 q = i ^ m。得 a1 * ( 1 + q + q^2 + q^3 + ...) 这虽然就成了等比数列，但是等比数列求和公式有分母，无法进行取模运算。即使求分母的逆元，但是若分母和m不互质，分母是没有逆元的(if the denominator and m are not coprime). 这时就需要发现技巧了。 1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n), 若最高次幂为偶数，那一项单独计算；否则，就用这个公式进行反复平方法（类似于快速幂的思想）在O(logn)时间内计算出一个几何级数的和。最多有m个这样的几何级数（等价划分的来的）求和。 note that 0^0 = 1. 实现见代码中的gp函数。 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; #define ll long long ll pow_mod(ll b, ll p, ll m) { ll res = 1; while (p) { if (p & 1) res = res * b % m; b = b * b % m; p >>= 1; } return res; } //若用公式，必须用逆元解决除数取模的问题// (q^(n+1) - 1) / (q - 1) % m，但不幸的是…… ll gp(ll q, ll n, ll m) { // 1 + q + q^2 + ... + q^n if (q == 0) return 1 % m; ll factor = 1, sum = 0, temp; while (n > 0) { if (n % 2 == 0) { temp = (factor * pow_mod(q, n, m)) % m; //偶数个和，先计算出幂指数最大的右边那项 sum = (sum + temp) % m; n--; } factor = (((1 + q) % m) * factor) % m; q = (q * q) % m; //仍然是反复平方法 n >>= 1; //底数平方一下，指数减半 } return (sum + factor) % m; } int main() { ios::sync_with_stdio(0); ll t; cin >> t; while (t--) { ll n, m, s; s = 0; cin >> n >> m; if (n < m) for (ll i = 0; i <= n; i++) s = (s + pow_mod(i, i, m)) % m; else { s = 1; // 0^0 = 1 for (ll i = 1; i < m; i++) { ll cnt = (n - i) / m; //项数 - 1(a1) ll a1 = pow_mod(i, i, m); //a1 ll q = pow_mod(i, m, m); if (q == 1) //小心公比为1 s = (s + a1 * (cnt + 1)) % m; else s = (s + ((a1* gp(q, cnt, m)) % m)) % m; } } cout << s << endl; } return 0; }

Suhana and Equation Problem Code: SEQUA

Submit
 

All submissions for this problem are available.   Suhana is studying following equation : 
f(N) = 00 + 11 + 22 + 33 + 44 + ... + NN

Can you solve f(N) % M before Suhana does? 

Input

First line contains T, number of test cases. 
First line of each test case contains N and M. 
 

Output

Output the required answer in new line.  

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 10^9
  • 1 ≤ M ≤ 10^3
 

Example

Input: 4 1 9 2 29 3 93 40 993 Output: 2 6 33 907

热门文章