UOJ 216 Jakarta Skyscrapers-白红宇

UOJ 216 Jakarta Skyscrapers

阅读量：6249 次

发布时间：2019-06-22

本文共 1226 字，大约阅读时间需要 4 分钟。

http://uoj.ac/problem/216

题意:给定A,B,C，如果集合中有数i,j(i>j)，那么集合就会增加i-j这个数，问有没有在初始集合为{A,B}400步内生成C的方案。

思路:我们用辗转相除法得到gcd(A,B),然后我们用A去减这个GCD，减出"二进制"数，然后就可以组成C了。

由于是log级别的，因此不会有超过400的方案。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define ll long longll c[50005][2],A,B,C,Gcd;int tot;ll read(){ ll t=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1;ch=getchar();} while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f;}ll gcd(ll a,ll b){ if (b==0) return a; else return gcd(b,a%b);}bool superjudge(){ if (C>A) {puts("-1");return 1;} if (A==C||B==C){puts("0");return 1;} ll Gcd=gcd(A,B); if (C%Gcd!=0){puts("-1");return 1;} return 0; }void work(ll A,ll B,ll C){ ll t=(A-C)/B,i; if (A==C) return; c[++tot][0]=A;c[tot][1]=B; for (i=1;i*2<=t;i*=2){ c[++tot][0]=A-i*B;c[tot][1]=i*B; c[++tot][0]=A;c[tot][1]=A-2*i*B; } A-=B*i; while (A>C){ if (A-i*B>=C){ c[++tot][0]=A; c[tot][1]=i*B; A-=i*B; } i/=2; }}void get_gcd(ll A,ll B){ if (A==Gcd||B==Gcd) return; work(A,B,A%B); get_gcd(B,A%B);}int main(){ A=read();B=read();C=read(); if (A