[BestCoder Round #3] hdu 4910 Problem about GCD

本文主要是介绍[BestCoder Round #3] hdu 4910 Problem about GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载自：

http://www.kuangbin.net/archives/hdu4910  慢慢学习.

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

 

 

 

 

 

 

很显然，需要找规律。 答案要么是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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#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-1long 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--);//值变化，防止死循环kfindfac(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;
}

这篇关于[BestCoder Round #3] hdu 4910 Problem about GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---