紧急求助对求取1000以上自然数末尾三位数的程序代码分析
请大家帮忙分析一下下面的这个abmodN()函数 ，后面附有函数的相关说明
// 用于计算a的b次方modn之后的值
int abmodN(__int64 a,int b,int n)
{
long t ;
t = 1;
while(b != 0)
{
if(b % 2 == 1)
t = (t * a)%n;
a =( a * a )%n;
b = b / 2;
}
//函数相关说明
这个abmodN()是要提取出大于等于1000以上的自然数的末尾三位数 然后赋值给t 返回保存
其中 a 是输入的底数，b是幂数，n是取模的值，且设n=1000,是固定值(对a和b的取值属性进一步示例说明 例如 25的5次方 其中a=25 ,b =5）
现在的问题是：
为什么要采用
if(b%2 ==1)
t = (t * a)%n;
a =( a * a )%n;
b = b / 2;
这样的函数体
我们一般用for() 先将a的b次方求出来 然后在模上1000 来求末尾三位数
我自己通过分析 大概了解到上面的那种求法比这个for（）这个求法在算法效率上更优，但是就是不知道他的这个程序的设计思路 是怎么设计出来的？ 请大家帮忙分析分析一下， 如果这样的一个题放到你手里， 在美语看到他这样的解答 你们会怎么做，要做到他这样的设计你们会怎么想？或者你觉得还有什么更好更快的方法来求解一个大于1000以上的自然数的末尾三位数，前提是这个1000以上的自然数首先要通过输入的一个随机自然数a并通过它的幂次b来求得 ，也就是说要系统只接受一个随机的自然数，然后里面有个幂次变量b从1开始递增，知道a的b次幂的值第一次大于等于1000，然后计算这个值的末尾三位数，并返回保存。
更希望大家能更多地从算法效率 时间 和空间占用率来帮忙解答本题，当然非常希望看到其他的见解，谢谢 算法代码分析 求模 取末尾三位数
[解决办法]
if(b % 2 == 1)
t = (t * a)%n;
a =( a * a )%n;
b = b / 2;
因为你是取n的模，所以中间每次结果对n取模都不会影响最终结果且还能使数据不止溢出。
因为a每次都是(a*a)%n,就是说每次算的时候a=a*a，而此时b=b/2,恰好算到这里的 a的b次幂的结果除了b/2舍掉的那个1之外就是对的。所以while开始时t=t*a先加上b/2舍掉的那个1.
算法没错，但是能想到还是听困难的。
在说用for来算，你每次取的中间结果也需要%n,否则可能会导致溢出。
[解决办法]
这个是很基础的同模定理
a^b很有可能超出int表示范围，只能这样写
[解决办法]
跟什么算法效率 时间 和空间占用率都没有关系
lz应该去了解一下int的表示范围和同模定理
[解决办法]
a的b次方可能溢出
[解决办法]
这样写你应该就能明白了
if(b % 2 == 1)
{
t = (t * a) % n;
}
a =( a * a ) % n;
b = b / 2;
我们知道：A^6 = (A^3)^2，A^7 = A * (A^3)^2
对于比n大的部分，取于取模的结果是没有影响的，可以先减掉n的整数倍，也就是可以先取模
即：a = (a * a) % n
[解决办法]
b % 2 == 1
这一句就是在b为奇数时，先乘一次，使乘下的幂为偶数。