ACM – UVa10006 – 快速幂

点击量:34

水题一发。无奈自己没有好好审清题意,另外快速幂居然写错了- =

快速幂在过程中修改a的值,但是我却计算成了在偶数时相乘,调试半天。看来还是咩有好好理解啊。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
ll p;
ll pow_mod(ll a, ll n)
{
    ll ans = 1;
    a %= p;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
// 3.
const int maxn = 10000000 + 10;
const int maxp = 700000;
int vis[maxn];
int prime[maxp];
// 筛素数
void sieve(int n)
{
    int m = (int) sqrt(n+0.5);
    memset(vis, 0, sizeof(vis));
    for(int i = 2; i <= m;i ++) if(!vis[i])
        for(int j = i*i; j <= n; j+=i) vis[j] = 1;
}
// 生成素数表
int gen_primes(int n)
{
    sieve(n);
    int c = 0;
    for(int i = 2; i <= n; i++) if(!vis[i])
        prime[c++] = i;
    return c;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    ll n;
    const int bound = 65000+10;
    gen_primes(bound);
    while(scanf("%lld", &n) && n!= 0)
    {
        // p is mod
        p = n;
        if(!vis[n])
            printf("%lld is normal.\n", n);
        else
        {
            bool find = 1;
            for(ll i = 2; i < n;i ++)
                if(pow_mod(i, n) != i)
                {
                    find = 0;
                    break;
                }
            if(find)
                printf("The number %lld is a Carmichael number.\n", n);
            else printf("%lld is normal.\n", n);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注