学步园

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<stdio.h>
#include<string.h>
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;
}