设为首页 加入收藏

TOP

POJ 2115.C Looooops“编程开发”
2017-12-11 09:18:48 】 浏览:232
Tags:POJ 2115.C Looooops 编程 开发

AC代码(C++):

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define INF 0xfffffff #define MAXN 100105 using namespace std; long long A,B,C,k; void exgcd(long long a, long long b, long long &d, long long &x, long long &y) { if(!b){d=a; x=1; y=0;} else { exgcd(b, a%b, d, y, x); y-=x*(a/b); } } int main(){ while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){ if(A+B+C+k==0)break; long long a,b,c,d,x,y; a = C; b = (long long)1<
            
              总结: 设循环了x次, A超过2^k(即loop)了y次, 则可以得到表达式Cx-(2^k)y=B-A. 这是一个不定方程, 可能有多种解, 而我们要求的是使x最小的那个解. 扩展欧几里得算法就是专门求形如ax+by=c的一个特殊的解的方法, 顺带求出a和b的最大公约数:
             

 

 

对形如ax+by=c的方程, 用扩展欧几里得算法求出x, y以及a, b的最大公约数d. 如果c%d!=0则无解, 如果有解, 则求x的最小值x0: 设dm=b/d, 则x0=((x*c/d)%dm+dm)%dm.

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++显示错误expected initializer.. 下一篇C++实现插入排序的代码

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目