Question

C语言问题，，求解惑，求解惑

今天是一个特别的日子，百年一遇的光棍节，2011.11.11，xym收到一个装着礼物的信封，是一位mm的XX书，里面是两个棒棒糖和一封信。
信里是一道智力题：
定义如果<x0,y0>和<x1,y1>满足x0-x1=y0-y1，则称这两个为等差对。
mm的问题是，问在<x,y>（0<=x,y<=n）<0,0>,<0,1>…<1,0>,<1,1>…<2,0>,
<2,1>…<n,0>…<n,1>…这(n+1)^2个有序对中存在多少个等差对？
但是xym因为昨晚听他们班的女生唱歌太晚睡觉了，严重影响状态，现在他只能请求各位scau未来的希望帮助他解决这个问题。

Input
第一行输入一个整数T(T<=1000)，表示case数。
下面T行有T个case，每个case只有一个整数n（1<=n<=10^9），表示0<=x,y<=n;但是由于测试的时候发现用scanf("%lld",&n)有bug，所以为了修正这个bug，请各位用long long读入的同学在读入前先赋0给变量，
例如 long long n=0; scanf("%lld",&n);
Output
每个case输出一行,表示等差对的数量，这个结果可能很大，只需最后结果%20111111即可。
Sample Input
2
2
100

Sample Output
5
338350

Hint注意不要让数据溢出，及时取模的处理

这个是我的程序：
#include<stdio.h>
main()
{
int T,j;
long long n=0,result=0;
scanf("%d",&T);
for(j=0;j<T;j++)
{
scanf("%lld",&n);
result=n*(n+1)%20111111;
result=result*(2*n+1)/6%20111111;
printf("%lld\n",result);
}
return 0;
}
等差对的个数经过证明就是n^2，，我这个程序应该也不会有数值溢出，，错哪里，求大神指教

Answer 1

问题的关键在于除以6，不能讲/6放在mod之后，否则就会出错 ，我给你个例子 7*8/2%6， 和 7*8%6/2 结果一样吗？
另外给你个小公式，应该能用到(a/b)%m = (a%mb) / b

Answer 2

如果如你所说，等差对的个数经过证明就是n^2，那你的结果就是要输出 (n^2) % 20111111
考虑到大数，把平方用加法来表示输出：
result = 0;
int nn = n % 20111111;
for ( long long k=0; k<n ; k++ )
{
result += nn ;
result %= 20111111 ;
}

追问

那个是打错了。。。是n的平方和

Answer 3

long long n=0,result=0;移到循环中去定义

如：
for(j=0;j<T;j++)
{
long long n=0,result=0;

scanf("%lld",&n);

追问

可以解释一下吗

追答

我不知道你的计算数对的算法是不是正确，但从你这段话提示中可得：
“但是由于测试的时候发现用scanf("%lld",&n)有bug，所以为了修正这个bug，请各位用long long读入的同学在读入前先赋0给变量，例如 long long n=0; scanf("%lld",&n);”
在调用scanf()函数给long long数据赋值时，一定要先将n置为0，这样才能保证n值的正确！

追问

按你说的方法改了后提交，依然不能通过。。计算数对的方法我想是没问题的，就是n的平方和，而且我那个程序在输入一些比较小的数是正确的，只是很大的数无法验证是否有问题

追答

这样试试吧
#include
int main ()
{
int T, j;
scanf ("%d", &T);
for (j = 0; j < T; j++)
{
long long n = 0, result = 0, i=1;
scanf ("%lld", &n);
for ( ; i<=n ; i++ )
{
result += i*i%20111111 ;
result %= 20111111 ;
}
printf ("%lld\n", result);
}
return 0;
}不成就算了，我不知道你的问题所在。