NYOJ-458 小光棍数

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 1 描述 最近Topcoder的XD遇到了一个难题，倘若一个数的三次方的后三位是111，他把这样的数称为小光棍数。他已经知道了第一个小光棍数是471,471的三次方是104487111，现在他想知道第m（m<=10000000000）个小光棍数是多少？ 输入 有多组测试数据。第一行一个整数n，表示有n组测试数据。接下来的每行有一个整数m。 输出 输出第m个小光棍数。 样例输入 1 1 样例输出 471 ******************************************************************************************************************************* 其实这个题不难，但还是不会的原因是不知道同余定理，或者是不懂同余定理。

      思路第一个光棍数是471=>以后的每个光棍数x的后三位都是471=> x00=471

      则由同余定理得 471≡x mod 1000=> x=1000k+471.

同余定理：

数学上的记法为： a≡ b(mod d) 可以看出当n<d的时候,所有的n都对d同商,比如时钟上的小时数,都小于12,所以小时数都是模12的同商. 对于同余有三种说法都是等价的,分别为: (1) a和b是模d同余的. (2) 存在某个整数n,使得a=b+nd . (3) d整除a-b. 可以通过换算得出上面三个说法都是正确而且是等价的. 证明 (1)、(2)、(3)等价： m=a%d==b%d; (a-m)=x*d; (b-m)=y*d; a-m-b+m=(x-y)*d; ************************************************************************************************************************************* 代码：

#include <stdio.h>int main(){    long long n,m;    scanf("%lld",&n);    while(n--)    {        scanf("%lld",&m);        printf("%lld\n",1000*(m-1)+471);    }    return 0; }