HDU 6624 (2019杭电第五场 1001) fraction (辗转相除求最小分数解 )

题意:分数取模的意义是 a/b = x(mod p),告诉你 p和x,求最小的分数解a/b

解:

#include <bits/stdc++.h>
#define ll long long
using  namespace std;
void gao(ll pa,ll pb,ll qa,ll qb,ll &x,ll &y){
	ll z = (pa+pb-1)/pb;
	if(z<=qa/qb){
		x = z;	y = 1;
		return ;
	}
	pa-=(z-1)*pb;	qa-=(z-1)*qb;
	gao(qb,qa,pb,pa,y,x);
	x+=(z-1)*y;
}
ll p,a,x,y;
int main()
{
	int _;
	for(scanf("%d",&_);_;_--){
		scanf("%lld %lld",&p,&a);
		gao(p,a,p,a-1,x,y);
		ll z = x*a - y*p;
		printf("%lld/%lld\n",z,x);	
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券