HNU_11720

    这个题目本来是一个数论课本的课后习题，最后可以得到结论sp=(p*p-1)/24-(p-1)/4（我暂时还没看懂怎么推导的……），这样就可以很容易的算出sp的值，于是就可以得到sp*rp=k*p+1，变形得sp*rp-p*k=1，又因为p是素数且可以证明gcd(sp,p)==1，所以这个方程必然有解，于是用拓展欧几里得求出rp即可。

#include
     
       #include
      
        long long int P; void gcd(long long int a, long long int b, long long int &x, long long int &y) {
   if(b == 0)         x = 1, y = 0; else     {
           gcd(b, a % b, y, x);         y -= x * (a / b);     } } void solve() {
   int i, j, k; long long int x, y, ans = (P * P - 1) / 24 - (P - 1) / 4;     gcd(ans, P, x, y);     printf("%lld\n", (x % P + P) % P); } int main() {
   int t, tt;     scanf("%d", &t); for(tt = 0; tt < t; tt ++)     {
           scanf("%lld", &P);         printf("Case #%d: ", tt + 1);         solve();     } return 0; }