【POJ】[1064]Cable master

问题描述

Cable master

[poj-1064] [3151927532608387] @vjudge

问题分析

对结果进行二分搜索
计算当前的mid可以分多少份
与k进行比较
判断条件也很好写

然而……

这是卡精度的一题
需要注意的是因为题意
所以最后结果不可以四舍五入
需要进行舍弃

而进制转换和double的灵异机制
导致这一题最后的数据处理会很麻烦

这里是因为逼得……
所以用了一种很逗的方式输出……

测试数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
long long exgcd(long long a,long long b,long long &x,long long &y) {
	if(b==0) {
		x=1,y=0;
		return a;
	}
	long long d=exgcd(b,a%b,y,x);
	y-=x*(a/b);
	return d;
}
int main() {
	long long x,y,m,n,L;
	while(scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&L)!=EOF) {
		long long t1,t2;
		long long d=exgcd(n-m,L,t1,t2);
		if((y-x)%d!=0)
			printf("Impossible\n");
		else {
			t1=t1*((x-y)/d);
			long long r=L/d;
			t1=(t1%r+r)%r;
			printf("%lld\n",t1);
		}
	}
	return 0;
}