注册 登录
编程论坛 C++教室

有个 问题向大家请教

lqqnjust 发布于 2008-07-18 12:05, 474 次点击
要求是:(a^p)%p==a   详见http://acm.pku.
  
我的代码是这样的:
#include <iostream>
using namespace std;
long int f(int p,int a)
{
     long int s=1;
    for(int i=0;i<p;i++)    s*=a;
    return s;
}
  
int  main()
{
    long int p,a;
    cin>>p>>a;
    while((p||a)!=0)
    {
        if(f(p,a)%p==a)  cout<<"yes"<<endl;
         else cout<<"no"<<endl;
        cin>>p>>a;
    }
    return 0;
}
可是老算不到正确的结果,是不是数据定义有错误啊,定义的太小了?
4 回复
#2
jzf20502008-07-18 13:18
楼主,你的程序基本没问题。
比如,你让P=3,A=2,那就可以输出“YES”;
如果说有问题的话,就是求次方函数的问题,一旦数值可大,就会出现越界。因为是次方,其实数值不用过大就会产生越界。你必须确保不越界。
#3
lqqnjust2008-07-18 20:54
有时算到负的结果出来了,当P=1105,a=3时
#4
aipb20072008-07-18 23:09
楼主,这个题不是描述题,不能想那么简单,需要分析的。
1:越界的问题,一般涉及多次幂运算,就要考虑越界,int值能装4byte
2:经验法则,为什么题目不直接叫你算a的p次幂?而要多加个模p的运算?这是有原因的。

解题关键:
(a*b)%p == (a%p)*(b%p)
这个应该不难证明吧!

然后题目,a^p可以在每一次乘运算后%p(模运算),这样一来,越界问题就解决了,因为运算子的范围被缩小到0-p
进一步:
幂运算,如果按a^p = a*a*a*a...这样做,那么算法复杂度为O(p)
如果a^p = ((a^2)^2)^2...这样做,那么算法复杂度为O(lgp)
时间上是有很大差别的

不知道题目限制的时间是多少,如果严格一点,那么
按第一种很可能 TLE
第二种 绝对AC
#5
lqqnjust2008-07-21 08:24
也对哦。我想也不能这么简单吧,呵呵,非常感谢哦
1