AOJ 0005：GCD and LCM
/*
求GCD和LCM
*/
#include <cstdio>
int a,b;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
while(~scanf("%d%d",&a,&b)){printf("%d %lld
",gcd(a,b),1LL*a*b/gcd(a,b));}
return 0;
}
POJ 1930：Dead Fraction
/*
将循环小数变回分数
*/
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits>
#include <cstdio>
using namespace std;
string s;
typedef unsigned long long ULL;
ULL gcd(ULL a,ULL b){return b?gcd(b,a%b):a;}
ULL Pow(unsigned int x){
ULL ans=1;
for(unsigned int i=0;i<x;i++)ans*=10;
return ans;
}
int main(){
while(cin>>s){
if(s=="0")break;
string digit=s.substr(2,s.length()-5);
unsigned int len=digit.length();
const ULL n=atoi(digit.c_str());
if(n==0){cout<<"0/1"<<endl;continue;}
ULL min_x=numeric_limits<ULL>::max();
ULL min_y = 0;
for(int i=1;i<=len;i++){
string first=digit.substr(0,len-i);
ULL x=Pow(len)-Pow(len-i);
ULL y=n-atoi(first.c_str());
ULL d=gcd(x, y);
x/=d;y/=d;
if(min_x>x){
min_x=x;
min_y=y;
}
}cout<<min_y<<'/'<<min_x<<endl;
}return 0;
}
POJ 2429：GCD & LCM Inverse
/*
题目大意：给出最大公约数和最小公倍数，满足要求的x和y，且x+y最小
题解：我们发现，(x/gcd)*(y/gcd)=lcm/gcd，并且x/gcd和y/gcd互质
那么我们先利用把所有的质数求出来Pollard_Rho，将相同的质数合并
现在的问题转变成把合并后的质数分为两堆，使得x+y最小
我们考虑不等式a+b>=2sqrt(ab),在a趋向于sqrt(ab)的时候a+b越小
所以我们通过搜索求出最逼近sqrt(ab)的值即可。
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#define C 2730
#define S 3
using namespace std;
typedef long long ll;
ll n,m,s[1000],cnt,f[1000],cnf,ans;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mul(ll a,ll b,ll n){return(a*b-(ll)(a/(long double)n*b+1e-3)*n+n)%n;}
ll pow(ll a, ll b, ll n){
ll d=1; a%=n;
while(b){
if(b&1)d=mul(d,a,n);
a=mul(a,a,n);
b>>=1;
}return d;
}
bool check(ll a,ll n){
ll m=n-1,x,y;int i,j=0;
while(!(m&1))m>>=1,j++;
x=pow(a,m,n);
for(i=1;i<=j;x=y,i++){
y=pow(x,2,n);
if((y==1)&&(x!=1)&&(x!=n-1))return 1;
}return y!=1;
}
bool miller_rabin(int times,ll n){
ll a;
if(n==1)return 0;
if(n==2)return 1;
if(!(n&1))return 0;
while(times--)if(check(rand()%(n-1)+1,n))return 0;
return 1;
}
ll pollard_rho(ll n,int c){
ll i=1,k=2,x=rand()%n,y=x,d;
while(1){
i++,x=(mul(x,x,n)+c)%n,d=gcd(y-x,n);
if(d>1&&d<n)return d;
if(y==x)return n;
if(i==k)y=x,k<<=1;
}
}
void findfac(ll n,int c){
if(n==1)return;
if(miller_rabin(S,n)){
s[cnt++]=n;
return;
}ll m=n;
while(m==n)m=pollard_rho(n,c--);
findfac(m,c),findfac(n/m,c);
}
void dfs(int pos,long long x,long long k){
if(pos>cnf)return;
if(x>ans&&x<=k)ans=x;
dfs(pos+1,x,k);
x*=f[pos];
if(x>ans&&x<=k)ans=x;
dfs(pos+1,x,k);
}
int main(){
while(~scanf("%lld%lld",&m,&n)){
if(n==m){printf("%lld %lld
",n,n);continue;}
cnt=0; long long k=n/m;
findfac(k,C);
sort(s,s+cnt);
f[0]=s[0]; cnf=0;
for(int i=1;i<cnt;i++){
if(s[i]==s[i-1])f[cnf]*=s[i];
else f[++cnf]=s[i];
}long long tmp=(long long)sqrt(1.0*k);
ans=1; dfs(0,1,tmp);
printf("%lld %lld
",m*ans,k/ans*m);
}return 0;
}
AOJ 0009：Prime Number
/*
求n以下的素数个数
*/
#include <cstdio>
const int N=1000000;
int p[N],n;
int main(){
for(int i=2;i<N;i++){
if(!p[i]){for(int j=i+i;j<N;j+=i)p[j]=1;}
}for(int i=2;i<N;i++)p[i]=p[i-1]+(!p[i]);
while(~scanf("%d",&n))printf("%d
",p[n]);
return 0;
}
POJ 3126：Prime Path
/*
从一个四位素数变成一个四位素数，
每次可以改变某个数字，但是改完后必须是素数
求最小步数
*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=10010;
bool p[N];
int T,vis[N];
string s1,s2;
int main(){
memset(p,true,sizeof(p));
for(int i=2;i<N;i++){
for(int j=i+i;j<N;j+=i)p[j]=0;
}scanf("%d",&T);
while(T--){
memset(vis,0,sizeof(vis));
cin>>s1>>s2;
queue<string> Q;
Q.push(s1); vis[atoi(s1.c_str())]=1;
while(!Q.empty()){
string now=Q.front();Q.pop();
if(now==s2)break;
int n=atoi(now.c_str());
for(int i=0;i<4;i++){
string tmp=now;
for(int j=0;j<10;j++){
if(i==0&&j==0)continue;
tmp[i]=j+'0';
int pos=atoi(tmp.c_str());
if(p[pos]&&!vis[pos]){
vis[pos]=vis[n]+1;
Q.push(tmp);
}
}
}
}cout<<vis[atoi(s2.c_str())]-1<<endl;
}return 0;
}
POJ 3292：Semi-prime H-numbers
/*
形似4n+1的被称作H-素数，两个H-素数相乘得到H-合成数。求h范围内的H-合成数个数
*/
#include <cstdio>
using namespace std;
const int N=1000010;
int h,p[N],u[N],cnt=0,com[N];
int main(){
for(int i=5;i<N;i+=4){
if(u[i])continue;
p[cnt++]=i;
for(int j=i*5;j<N;j+=i*4)u[j]=1;
}for(int i=0;i<cnt;i++){
for(int j=0;j<=i;j++){
long long t=p[i]*p[j];
if(t>N)break;
com[t]=1;
}
}for(int i=1;i<N;i++)com[i]=com[i-1]+com[i];
while(~scanf("%d",&h)&&h)printf("%d %d
",h,com[h]);
return 0;
}
POJ 3421：X-factor Chains
/*
给出一个数字n,问n的因子组成的满足任意前一项都能整除后一项的序列的最大长度，
以及所有不同序列的个数
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL x[25]={1},n;
int main(){
for(int i=1;i<25;i++)x[i]=i*x[i-1];
while(~scanf("%lld",&n)){
LL ans=0,base=1;
for(LL i=2;i*i<=n;i++){
if(n%i==0){
LL cnt=0;
while(n%i==0){++cnt;n/=i;}
ans+=cnt;
base*=x[cnt];
}
}if(n>1)ans+=1;
printf("%lld %lld
",ans,x[ans]/base);
}return 0;
}
POJ 3641：Pseudoprime numbers
/*
给出两个数n和m判断n是否是伪素数，即n不是素数但是m的n次对n取模等于m对n取模
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL mul(LL x,LL y,LL mod){return (x*y-(long long)(x/(long double)mod*y+1e-3)*mod+mod)%mod;}
LL pow(LL a,LL b,LL P){LL t=1;for(;b;b>>=1,a=mul(a,a,P))if(b&1)t=mul(t,a,P);return t;}
bool isprime(LL x){
for(int i=2;i*i<x;i++)
if(x%i==0)return 0;
return 1;
}LL n,m;
int main(){
while(scanf("%lld%lld",&n,&m)&&(n+m)){
if(isprime(n))puts("no");
else if(pow(m,n,n)==m%n)puts("yes");
else puts("no");
}return 0;
}
POJ 1995：Raising Modulo Numbers
/*
快速幂性质裸题
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL mul(LL x,LL y,LL mod){return (x*y-(long long)(x/(long double)mod*y+1e-3)*mod+mod)%mod;}
LL pow(LL a,LL b,LL P){LL t=1;for(;b;b>>=1,a=mul(a,a,P))if(b&1)t=mul(t,a,P);return t;}
int T,n;
LL a,b,mod;
int main(){
scanf("%d",&T);
while(T--){
LL ans=0;
scanf("%lld%lld",&mod,&n);
while(n--){
scanf("%lld%lld",&a,&b);
ans=(ans+pow(a,b,mod))%mod;
}printf("%lld
",ans);
}return 0;
}