HDU 4910 Problem about GCD (数论)

HDU 4910

Problem about GCD

求小于等于 N 的与N互质的所有数的乘积mod N

Problem about GCD

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 26 Accepted Submission(s): 6

Problem Description

Given integer m. Find multiplication of all 1<=a<=m such gcd(a, m)=1 (coprime with m) modulo m.

Input

Input contains multiple tests, one test per line. Last line contains -1, it should be skipped.[Technical Specification] m <= 10^18

Output

For each test please output result. One case per line. Less than 160 test cases.

Sample Input

1 2 3 4 5 -1

Sample Output

0 1 2 3 4

Source

BestCoder Round #3

很显然,需要找规律。 答案要么是N-1,要么是1.

答案为N-1的情况是: 1 2 4 此外 如果 N!=4 && N%4 == 0 答案是1 如果N为偶数,要求N/2 是 p^k的形式; 如果N为奇数,要求N是p^k的形式。

/* ***
Author :kuangbin
Created Time :2014/8/3 19:24:03
File Name :D.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

/* *************************************************
* Miller_Rabin 算法进行素数测试
* 速度快,可以判断一个 < 2^63 的数是不是素数
*
**/

const int S = 20; //随机算法判定次数,一般8~10就够了

// 计算ret = (a*b)%c a,b,c < 2^63
long long mult_mod(long long a,long long b,long long c)
{
a %= c;
b %= c;
long long ret = 0;
long long tmp = a;
while(b)
{
if(b & 1)
{
ret += tmp;
if(ret > c)ret -= c;//直接取模慢很多
}
tmp <<= 1;
if(tmp > c)tmp -= c;
b >>= 1;
}
return ret;
}

// 计算 ret = (a^n)%mod
long long pow_mod(long long a,long long n,long long mod)
{
long long ret = 1;
long long temp = a%mod;
while(n)
{
if(n & 1)ret = mult_mod(ret,temp,mod);
temp = mult_mod(temp,temp,mod);
n >>= 1;
}
return ret;
}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x*2^t 中间使用二次判断
// 是合数返回true, 不一定是合数返回false
bool check(long long a,long long n,long long x,long long t)
{
long long ret = pow_mod(a,x,n);
long long last = ret;
for(int i = 1;i <= t;i++)
{
ret = mult_mod(ret,ret,n);
if(ret == 1 && last != 1 && last != n-1)return true;//合数
last = ret;
}
if(ret != 1)return true;
else return false;
}
//**
// Miller_Rabin算法
// 是素数返回true,(可能是伪素数)
// 不是素数返回false
//**
bool Miller_Rabin(long long n)
{
if( n < 2)return false;
if( n == 2)return true;
if( (n&1) == 0)return false;//偶数
long long x = n - 1;
long long t = 0;
while( (x&1)==0 ){x >>= 1; t++;}

srand(time(NULL));/* *************** */

for(int i = 0;i < S;i++)
{
    long long a  = rand()%(n-1) + 1;
    if( check(a,n,x,t) )
       return false;
}
return true;

}

//**
// pollard_rho 算法进行质因素分解
//
//
//*
long long factor[100];//质因素分解结果(刚返回时时无序的)
int tol;//质因素的个数,编号0~tol-1

long long gcd(long long a,long long b)
{
long long t;
while(b)
{
t = a;
a = b;
b = t%b;
}
if(a >= 0)return a;
else return -a;
}

//找出一个因子
long long pollard_rho(long long x,long long c)
{
long long i = 1, k = 2;
srand(time(NULL));
long long x0 = rand()%(x-1) + 1;
long long y = x0;
while(1)
{
i ++;
x0 = (mult_mod(x0,x0,x) + c)%x;
long long d = gcd(y - x0,x);
if( d != 1 && d != x)return d;
if(y == x0)return x;
if(i == k){y = x0; k += k;}
}
}
//对 n进行素因子分解,存入factor. k设置为107左右即可
void findfac(long long n,int k)
{
if(n == 1)return;
if(Miller_Rabin(n))
{
factor[tol++] = n;
return;
}
long long p = n;
int c = k;
while( p >= n)
p = pollard_rho(p,c–);//值变化,防止死循环k
findfac(p,k);
findfac(n/p,k);
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);

long long n;
while(scanf("%I64d",&n) == 1)
{
    if(n == -1)break;
    if(n <= 1)
    {
        printf("0\\n");
        continue;
    }
    if(n == 1 || n == 2 || n == 4)
    {
        printf("%I64d\\n",n-1);
        continue;
    }
    if(n != 4 && n % 4 == 0)
    {
        printf("1\\n");
        continue;
    }
    tol = 0;
    if(n%2 == 0)
    {
        findfac(n/2,107);
        sort(factor,factor+tol);
        bool flag = true;
        for(int i = 1;i < tol;i++)
            if(factor\[i-1\] != factor\[i\])
            {
                flag = false;
                break;
            }
        if(flag)printf("%I64d\\n",n-1);
        else printf("1\\n");
    }
    else
    {
        findfac(n,107);
        sort(factor,factor+tol);
        bool flag = true;
        for(int i = 1;i < tol;i++)
            if(factor\[i-1\] != factor\[i\])
            {
                flag = false;
                break;
            }
        if(flag)printf("%I64d\\n",n-1);
        else printf("1\\n");
    }
}
return 0;

}

------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 319.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
0%