同余——推柿子例题
题意:
设青蛙 A 的出发点坐标是 ,青蛙 的出发点坐标是 。青蛙 一次能跳 米,青蛙 一次能跳 米,两只青蛙跳一次所花费的时间相同。纬度线总长 米。现在要你求出它们跳了几次以后才会碰面。
题解:
设
则有注意这里a可能为负数,只对非负整数有意义,所以处理一下:若
那么,接下来我们求
由可解出就是
设,那么
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 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include<bits/stdc++.h> using namespace std; typedef long long ll; ll p1,p2,m,n,l,a,b,x,y; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x = 1,y = 0; return a; } ll d = exgcd(b,a%b,y,x); y -= (a/b)*x; return d; }
int main() { cin>>p1>>p2>>m>>n>>l;
ll a = n-m,b = l,c = p1-p2; if(a<0)a = -a,c = -c; ll d = exgcd(a,b,x,y); if(c%d)cout<<"Impossible\n"; else{ cout<<(c/d*x%(b/d)+(b/d))%(b/d)<<endl; } return 0; }
|
题意:给n个人,每个人有初始位置,和每年可以走过的洞穴数目及其存活寿命,求洞穴数至少有多少个保证n个人永远不会相遇。
题解:
这题其实和青蛙那题很像,也是给初始位置和每年走过的距离,不同的地方在于,本题求的是不相遇且多了一个寿命的限制。
对于任意两个人来说有:
其中:代表初始位置,和是每年走过的洞穴数,是相遇的时间,是洞穴的数目。
我们先一遍找到初始位置最大的洞穴编号,以次为起点枚举答案,即洞穴数目m,之后我们再去。
那么怎么呢?我们要这些人永远不会相遇,那对于任意两个人而言,我们解出的相遇时间x(用)要么是无解,要么,表示寿命,即在相遇之前就死掉了,所以还是不会相遇的
那么我们找到的第一个符合条件的就是答案。
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include<bits/stdc++.h> using namespace std; const int N = 110; int maxc,C[N],p[N],l[N]; int n; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x = 1,y = 0; return a; } int d = exgcd(b,a%b,y,x); y -= (a/b)*x; return d; } bool judge(int m) { for(int i = 1;i<=n;i++) { for(int j = i+1;j<=n;j++) {
int a = p[j]-p[i],b = m,c = C[i]-C[j],x = 0,y = 0; if(a<0)a = -a,c = -c; int d = exgcd(a,b,x,y); if(c%d==0) { int ans = ((c/d)*x%(b/d)+(b/d))%(b/d); if(ans<=min(l[i],l[j]))return false; } } } return true; }
int main() { cin>>n; for(int i = 1;i<=n;i++) { cin>>C[i]>>p[i]>>l[i]; maxc = max(maxc,C[i]); } for(int i = maxc;;i++) { if(judge(i)) { cout<<i<<endl; return 0; } } return 0; }
|