Rexdf

The devil is in the Details.

Zoj-3753

| Comments

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.

Sample Input

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

Sample Output

2 2
No answer
8 6
10 5

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

题意解释：

这题还是比较好做的，我当做最简单题来做的。很容易对原式变形得到:这样问题就变形了对\(A \times B\)这个数进行因式分解即可。A、B范围是\(10^9\)，这样分别对A、B因式分解只需要考虑小于\(10^5\)的素数测试就好了。另外估算一下：① \( 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times \cdots \times 29 = 6,469,693,230 > 1 \times 10^9\) ，这里最多10个素数；② \( 2^{60}=1,152,921,504,606,846,976 > 1 \times 10^{18}\)即指数和最大不超过60。因此这个计算过程是可以暴力进行的。也就是说对\(A \times B\)的每个因子进行一次枚举即可。设\(A \times B\)的一个因子是\(x_0\)，那么就这样暴力下去即可以解决了。

代码

#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);
        if(-1==ans1)printf("No answer\n");
        else printf("%lld %lld\n",ans1,ans2);
	}
	return 0;
}

Comments