静态手机网站建设的基本特点,网站备案去哪找接入商,怎么建立一个网站,建模教程正题
题目链接:https://atcoder.jp/contests/arc122/tasks/arc122_c 题目大意
一个数对开始是(0,0)(0,0)(0,0)#xff0c;每次可以选择一个数加一或者让一个数加上另一个数#xff0c;求使得第一个数变成nnn的方案。步数不超过130130130。 1≤n≤10181\leq n\leq 10^{18}1≤…正题
题目链接:https://atcoder.jp/contests/arc122/tasks/arc122_c 题目大意
一个数对开始是(0,0)(0,0)(0,0)每次可以选择一个数加一或者让一个数加上另一个数求使得第一个数变成nnn的方案。步数不超过130130130。
1≤n≤10181\leq n\leq 10^{18}1≤n≤1018 解题思路
官方是斐波那契但是我考试的时候过法比较神奇。
看上去比较像更相减损但是不知道第二个数是多少感觉我们应该能找到一个数对(n,k)(n,k)(n,k)使得它更相减损的步骤很少。
考虑的分散一点设nxkknxkknxkk。那么我们相当于要找到一个xxx使得xkkk1x\frac{xkk}{k}\frac{1}{x}kxkkx1。
然后解出来得到x5−12x\frac{\sqrt 5-1}{2}x25−1其实就是黄金分割率。
所以我们让kn×5−12kn\times \frac{\sqrt 5-1}{2}kn×25−1然后更相减损下去之后会发现有点误差我们前后各枚举100001000010000找到一个满足条件的就好了。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecmath
#define ll long long
using namespace std;
ll n;vectorll z;
void print(ll x,ll y){if(!x){while(yz.size()130)y--,z.push_back(2);return;}if(!y){while(xz.size()130)x--,z.push_back(1);return;}if(xy) print(x,y-x),z.push_back(4);else print(x-y,y),z.push_back(3);
}
signed main()
{scanf(%lld,n);double M(sqrt(5.0)-1.0)*(double)n/2.0;ll mM;for(ll imax(m-10000,0ll);im10000;i){print(n,i);if(z.size()130){z.clear();continue;}printf(%lld\n,z.size());for(ll i0;iz.size();i)printf(%lld\n,z[i]);break;}return 0;
}
