QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355186#5103. Fair Divisionucup-team052#WA 1ms3720kbC++23911b2024-03-16 14:15:422024-03-16 14:15:43

Judging History

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

  • [2024-03-16 14:15:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3720kb
  • [2024-03-16 14:15:42]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

using LL=long long;


const LL INFLL=LL(2e18);

int n;
LL m;
LL pwn[2005];

LL ad(LL x,LL y){
	return x+y<INFLL?x+y:INFLL;
}

LL mu(LL x,LL y){
	return x<=INFLL/y?x*y:INFLL;
}

LL po(LL x,LL y){
	LL z=1;
	while(y){
		if(y&1)z=mu(z,x);
		if((y>>=1))x=mu(x,x);
	}
	return z;
}

int main(){
	cin>>n>>m;
	rep(i,1,2000){
		pwn[i]=po(i,n);
		assert(pwn[i]>=0);
		assert(pwn[i]>=pwn[i-1]);
	}
	rep(q,2,2000)if(pwn[q]<INFLL){
		rep(p,1,q-1)if(__gcd(p,q)==1){
			LL fm=pwn[q]-pwn[q-p];
			LL fz=p*(pwn[q]/q);
			
			LL g=__gcd(fz,fm);
			/*if(g!=1){
				printf("%d %d\n",p,q);
			}*/
			// assert(g==1);
			
			fz/=g,fm/=g;
			if(m%fm==0){
				printf("%d %d\n",p,q);
				exit(0);
			}
		}
	}
	puts("impossible");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3720kb

input:

13 382475111752106101

output:

impossible

result:

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