最近又開始做ACM了。原因是，我在學校里面找了份兼職，做ACM興趣班的助教。
任務(wù)是給大一的新生講一些ACM的入門知識。
雖然講的東西很基礎(chǔ)很簡單，但我覺得他們的潛力巨大，很快就能達到跟我一樣的水平。。
所以我自己也得補下課啦。
這次我下決心，堅決不做一道水題！
我放棄了原來在POJ賬號，轉(zhuǎn)戰(zhàn)HOJ，因為這樣我才不會為了題目數(shù)量而刷水題。
我覺得以前真的很傻逼，老是挑著做一些自己已經(jīng)會了的題目，還總是抱怨自己的水平一直沒提高。
整天刷水題，水平他媽的能提高么。
人都是很懶的，懶得動腦子，只是享受敲完一道水題后ac的感覺，還很有成就感。
但這樣子有什么用，遇到難題的時候，始終還是想不出來，還以為是自己腦子不好使。
實際上不是的，只要克服惰性，多思考問題，每個人的腦子都是很好使的。
我挑戰(zhàn)的第一道難題，呵呵，對我來說比較難的題，就是這道。
想了一下發(fā)現(xiàn)了這個規(guī)律：
(A*B)%M = ((A%M)*(B%M))%M
演算一下就可以得出這個的。
對與輸入中的一個數(shù)字，可以分別計算出：
A%M
A^2 %M
A^4 %M
...
然后再相乘取模就行了。
這樣二分一下，就很好辦了。
這是我自己克服了懶惰動了腦子想出來的！我他媽的很自豪！
#include <stdio.h>
__int64 N, K, A, B, C, d, i, n, ans;
#define M 200907
int main()
{
scanf("%I64d", &N);
while (N--) {
scanf("%I64d%I64d%I64d%I64d", &A, &B, &C, &K);
if (B - A == C - B) {
ans = ((A%M) + (((K-1)%M)*((B-A)%M)%M))%M;
} else {
d = (B/A)%M;
n = K - 1;
ans = A%M;
for (i = 0; (1LL << i) <= n; i++) {
if (n & (1LL << i))
ans = (ans*d)%M;
d = (d*d)%M;
}
}
printf("%I64d\n", ans);
}
return 0;
}