1124. 整数幂

Andrew-Malcom

include

using namespace std;
int qpow(int a,int b,int c)
{
        int ans=1;
        while(b){
                if(b&1) ans=(ans*a)%c;
                a=(a*a)%c;
                b=b>>1;
        }
        return ans;
}
int main()
{
        int a,b,c;
        while(1==1){
                cin>>a>>b>>c;
                if(a==0&&b==0&&c==0) break;
                else cout<<qpow(a,b,c)<<endl;
        }
}
NBC++

快速幂取模

include

using namespace std ;
int mod (int a,int b,int c);
int main () {
int a,b,c ;
while (cin >> a >> b >> c){
if (!a & !b & !c)
break ;
cout << mod (a,b,c) << endl;
}
}

int mod (int a,int b,int c){
int result =1 ;
a %= c ;
while (b ){
if (b % 2){
result = a ;
result %= c ;
b – ;
}
a = (a
a) %c ;
b /= 2 ;
}
return result ;
}

Deuchie

看到这题那么高的通过率我猜想可以暴力,果然如此。

#include "bits/stdc++.h"

using namespace std;
using u64 = uint64_t;

int main() {
    for (u64 a, b, c; cin >> a >> b >> c, a;) {
        u64 ans = a % c;
        for (u64 i = 1; i < b; ++i) {
            ans = (ans * a) % c;
        }
        cout << ans << '\n';
    }
}

正解是快速幂,也就是这个:

#include "bits/stdc++.h"

using namespace std;
using u64 = uint64_t;

template <typename UInt> UInt ipow(UInt const kBase, UInt const kExp, UInt const kMod) {
    UInt ret = 1;
    for (UInt i = kExp, base = kBase % kMod; i; i >>= 1) {
        if (i & 1) {
            ret = ret * base % kMod;
        }
        base = base * base % kMod;
    }
    return ret;
} // quick power algorithm for (a^b) % kMod.

int main() {
    for (u64 a, b, c; cin >> a >> b >> c, a;) {
        cout << ipow(a, b, c) << '\n';
    }
}

(直接把之前写的模板套了上去)

algsCG
#include <bits/stdc++.h>
using namespace std;

int power(int a,int b,int p)
{
    int res=1%p;// 最低位为1
    while(b){
        if(b&1)res=res*1ll*a%p;// ci为1,需要乘以a
        a=a*1ll*a%p;// 每次a都平方
        b>>=1;
    }
    return res;
}

int main()
{
    int a,b,c;
    while(1)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(!a&&!b&&!c)break;
        else printf("%d",power(a,b,c));
    }
    return 0;
}
10175101249

天啦噜居然又有一千多组数据

Master X

这个连快速幂都不用的说?
(机房网真差……

kingno

无语,平常自己做不来,考试一考就做得来了

你当前正在回复 博客/题目
存在问题!