# Zoj-3753

Simple Equation

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are many Equations. Some are difficult to solve, for example: an xn + an-1 xn-1 + .. + a0 = 0. In this problem, you are given a simple equation: AX + BY = XY. To simplify the problem, here A, B, X, Y are positive integers. Your task is to find the solution (X, Y) of this equation where X is not less than M. If there are multiple solutions, you should choose the solution with the minimal X + Y. If there are still ties, you should choose the solution with the minimal X.

#### Input

There are multiple test cases (about 3000). For each test case: There is only one line contains three integers A, B (1 <= A, B <= 10 ^ 9) and M (1 <= M <= 10 ^ 18).

#### Output

For each test case, output X and Y. If there is no valid solution, output “No answer” instead.

1 1 2
1 1 3
3 4 8
3 4 9

#### Sample Output

2 2
8 6
10 5

Author: LIANG, Mingqiang Source: ZOJ Monthly, January 2014

#### 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

//分解质因数
//prime_factor()传入n, 返回不同质因数的个数
//f存放质因数，nf存放对应质因数的个数
//先调用initprime()，其中第二个initprime()更快

#define PSIZE (95592+5)
long long plist[PSIZE];
int pcount=0;
int prime(long n){
int i;
if ((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))
return 0;
for (i=0;plist[i]*plist[i]<=n;++i)
if (!(n%plist[i]))
return 0;
return n>1;
}
void initprime(){
int i;
for (plist[pcount++]=2,i=3;i<100000;++i)
if (prime(i))
plist[pcount++]=i;
}
int prime_factor(long n, long * f, int *nf) {
int cnt = 0;
long n2 = sqrt((double)n);
for(int i = 0; n > 1 && plist[i] <= n2; ++i)
if (n % plist[i] == 0) {
for (nf[cnt] = 0; n % plist[i] == 0; ++nf[cnt], n /= plist[i]);
f[cnt++] = plist[i];
}
if (n > 1) nf[cnt] = 1, f[cnt++] = n;
return cnt;
}

long long mod_pow(long p,int k){
long long ret=1,q=p;
while(k){
if(k&1)ret*=q;
k>>=1;
q=q*q;
}
return ret;
}

long A,B,mid;
long long M;
long a[15],b[15],c[15];
int an[15],bn[15],cn[15];
int acnt,bcnt,ccnt;

long long ans1,ans2;
int v[15];

void dfs(int cnt){
if(cnt==ccnt){
long long test=1,t1,t2;
for(int i=0;i<ccnt;i++){
test*=mod_pow(c[i],v[i]);
}
t1=B+test;
t2=1LL*A*B/test+A;
if(t1>=M){
if(-1==ans1 || t1+t2<ans1+ans2 || (t1+t2==ans1+ans2 && t1<ans1))ans1=t1,ans2=t2;
}
return;
}
for(int i=0;i<=cn[cnt];i++){//第cnt+1个素数可以取值0...cnt
v[cnt]=i;
dfs(cnt+1);
}
}

int main(){
initprime();
//cout<<pcount<<endl;
while(~scanf("%ld%ld%lld",&A,&B,&M)){
//mid=sqrt(A)*sqrt(B)+0.6;
acnt=prime_factor(A,a,an);
bcnt=prime_factor(B,b,bn);
ccnt=0;
for(int i=0,j=0;i<acnt || j<bcnt;){
if((i<acnt && j<bcnt && a[i]<b[j]) || (j==bcnt && i<acnt)){
c[ccnt]=a[i];
cn[ccnt]=an[i];
ccnt++;
i++;
}
else if((i<acnt && j<bcnt && a[i]>b[j]) || (i==acnt && j<bcnt)){
c[ccnt]=b[j];
cn[ccnt]=bn[j];
ccnt++;
j++;
}
else{
c[ccnt]=a[i];
cn[ccnt]=an[i]+bn[j];
ccnt++;
i++;
j++;
}
}
ans1=-1;
dfs(0);