QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66061#5103. Fair Divisiondani_tro#WA 352ms3212kbC++141.8kb2022-12-06 03:24:012022-12-06 03:24:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 03:24:02]
  • 评测
  • 测评结果:WA
  • 用时:352ms
  • 内存:3212kb
  • [2022-12-06 03:24:01]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

long long n, p, q;

double res = 0.0, f, st;

double pow1(double q, int st)
{
	if(st == 0)return 1.0;
	if(st == 1)return q;
	double ans = pow1(q, st / 2) * pow(q, st / 2);
	if(st % 2 == 0)ans *= q;
	return ans;
}

bool tr(long long p, long long q, long long m)
{
	long long p1 = 1, q1 = 1;
	double f = p * (1.0 / q);
	double tmp = f;
	long long res = 0;
	
	for(int i = 0; i < n; i++)
	{
		p1 *= p;
		//if(p1 < p)return false;
		if(p1 > m || q1 > m)return false;
	}
	//if(p == 1 && q == 3)cout << res << endl;
	for(int i = 0; i < n; i++)
	{
		res += p1 * q1;
		//cout << p1 << " " << q1 << endl;
		p1 /= p;
		q1 *= q;
		if(p1 > m || q1 > m || res > m || res < p)return false;
		if(q1 < q)return false;
	}
	//m *= q1;
	for(int i = 0; i < n - 1; i++)
	{
		if(res % q == 0)res /= q;
	}
	//if(p == 1 && q == 2)cout << res << endl;
	//double kt = m;
	//kt /= res;
	//long long ts = round(kt);
	//if(p == 1 && q == 2)cout << kt <<  " " << ts << " " <<setprecision(41) << kt - ts  << endl;
	//cout << m << " " << res << endl;
	if(m % res != 0)return false;
	return true;
}

int main()
{
	/*int n = 6;
	q = 2 * (1.0 / 3);
	int m = 91000;
	cout << m * ( 2 / (pow(3, n) - (pow(3 - 2, n)))) << endl;
	st = 1.0;
	for(int i = 0; i < n - 1; i++)st *= (1 - q);
	
	for(int i = 1; i <= 10000; i++)
	{
		res += 91000 * q * (st);
		for(int j = 0; j < n; j++)st *= (1 - q);
	}
	cout << res << endl;
	*/
	
	long long m;
	cin >> n >> m;
	if(m < n)
	{
		cout << "impossible\n";
		return 0;
	}
	
	for(int q = 1; q < 10000; q++)
	{
		for(int p = q - 1; p > 0; p--)
		{
			if(tr(p, q, m) == true)
			{
				cout << q - p << " " << q << endl;
				return 0;
			}
		}
	}
	
	cout << "impossible\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 352ms
memory: 3212kb

input:

13 382475111752106101

output:

impossible

result:

wrong answer 1st lines differ - expected: '17 28', found: 'impossible'