Input
The input consist of three integers A,B,C; 1<= A <=10000; 1<= B <=10^9; 1<=C<=10000; three 0 sign the end of the input
Output
The output will be a single integer——(A^B)%C. For example,A=2,B=4,C=5, then the result is (2^4)%5 = (2*2*2*2)%5 = 1.
我就是感觉B太大了不好处理。  
请各位指点应该怎么办得好，让我有个大致的思路来解决这道题。

pow(A,B)%C，，这个不行，B太大不好处理怎么说？还是要求时间上的限制？

有时间上的限制   就是还要考虑算法

这里有个求模算法：http://topic.

#include<iostream>
using namespace std;
//
int S_mod(int n,int x,int m);
int main()
{
    int n,x,m;
    int result;
    cout<<"Pleaase input three number"<<endl;
    cout<<"n=  x=  m="<<endl;
    cin>>n>>x>>m;
    //something  
    cout<<"n="<<n<<"  "<<"x="<<x<<"  "<<"m="<<m<<endl;
    cout<<"(n^x)mod(m)=";
    result=S_mod(n,x,m);
    cout<<result<<endl;
    return 0;
}

int S_mod(int n,int x,int m)
{
    int tem,tem2=1,count,tem3;
    tem=n%m;
    if((x&1))   //x 的奇偶性
    {
        tem2=tem%m;   //x 为奇数
        x-=1;
    }
    tem3=tem;
    for(count=0;count<x/2;count++)
    {
        tem3=(tem3*tem3)%m;
    }
    tem3=(tem3*tem2)%m;
    return tem3;
}

这个好像还不错哦
不过有些地方不懂就是那个x&1是什么意思？
还有这是我看到的另外的一个函数int Solve(int A, int B, int C)
{
      int t = 1;
      while (B>0)
      {
               if (B&1) {  t *= A;   t %= C}
               A *= A;  A%=C;
               B  >>= 1;
       }
      return t;
}   不过我就是 if (B&1)和B  >>= 1; 这两个地方不怎么明白。能解释解释吗？详尽更好

你这个网站不怎么好看啊  还要注册才行啊

就是x与1作位与 若为1 则整数个位为1，是奇数；0则个位为0，是偶数

int Solve(int A, int B, int C)    他的A 相当于我的 n ，B相当于 x,C相当于m
{
      int t = 1;
      while (B>0)
      {
               if (B&1) {  t *= A;   t %= C} 判断B 的奇偶性 提出首部的余数保留用以下一步求整体的余数
               A *= A;  A%=C;
               B  >>= 1;   这里是把B右移一位，也就是数B除以2 他这里是消弱其指数，也就是B的值，对应的n^m中的m
       }                    这里的用处是控制他的次数
      return t;
}                                                                             这里为了方便所以用了他的平方
其实 n^x mod(m) => (n mod(m))^x mod(m) => x 为偶数时(n mod(m))^2^(x/2)mod(m)=>{[(n mod(m))^2 mod(m)]^(x/2)}mod(m) 后面的则照上一步的方法
                                          x 为奇数时 提出 n mod(m)   这时次数是偶数了 遵照上面的方法了~~                      

[ 本帖最后由 yyblackyy 于 2010-4-3 21:42 编辑 ]

收到的鲜花

• 尹卫 于 2010-04-03 22:20 送鲜花  1朵   附言：解决了我的问题

唉  这些语法问题  
不过现在有懂得多一点了，谢了。

学计算机不知道CSDN，可惜！