首页 > 代码库 > POJ 1061

POJ 1061

2024-07-13 13:36:07   213人阅读

约会果然是件头疼的问题

看起来很简单

列了个式子就不知道怎么做了

数论题

欺负我数学不好

Attention：

(Ax+b)%C==0

有解条件为 b%gcd（A，C）==0;

证明在代码里

 1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4  5 long long x,y,m,n,L,dist; 6 //辗转相除求最大公约数 7 int gcd(int a,int b) 8 { 9     if(b==0)return a;10     return gcd(b,a%b);11 }12 // 把跳的慢的视为相对静止13 int main()14 {15     while(cin>>x>>y>>m>>n>>L)16     {17         //计算出两只青蛙的距离差18         //先比较快慢19         if(m>n)20             dist=(y-x+L)%L;21         else22         {23             dist=(x-y+L)%L;24             int temp=m;25             m=n;26             n=temp;27         }28 29         //现在证明判断条件30         //等式为： (i*L+dist)%(m-n)==031         //若有解 let t = gcd（L,m-n)32         //let L = ct;m-n = bt;33         //ict +dist = bkt34         //dist = (bk - ic)t35         //dist % t = 0; 36         if(dist%gcd(m-n,L)!=0)37         {38             cout<<"Impossible"<<endl;39             continue;40         }41         long long k=0;42         int i =0;43         for(int i=0;; i++)//暴力来试出结果44         {45             if((i*L+dist)%(m-n)==0)46             {47                 k=(i*L+dist)/(m-n);48                 break;49             }50         }51         cout<<k<<endl;52     }53     return 0;54 }


联系
我们