• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[cf1427E]Xum

开发技术 开发技术 4小时前 2次浏览

假设$x$的最高位为$2^{t}$(即$2^{t}le x<2^{t+1}$),并构造出$y=2^{t}xoplus x$,不难发现两者仅在第$t$位上均为1,那么根据异或的性质可得$y=(2^{t}+1)x-2^{t+1}$

由于$x$为奇数,即$(x,2^{t+1})=1$,进而也即$(x,y)=1$

通过扩欧求出一组$ax+by=1$的解,并调整使得$0<ale 2y$且$aequiv 1(mod 2)$,对应的$-2xle b<0$,根据奇偶性可得$ax$为奇数(且$by$为偶数),那么$ax+by=1$即等价于$axoplus (-b)y=1$,由此计算可得

另外,计算过程中需要实现乘法,这借助类似快速幂的做法实现即可

最终操作次数(和时间复杂度)约为$o(log n)$,数字范围约为$2n^{3}$,可以通过

[cf1427E]Xum[cf1427E]Xum

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 struct Data{
 5     int p;
 6     ll x,y;
 7 };
 8 vector<Data>ans;
 9 ll n,m,x,y;
10 void calc(ll n,ll m){
11     m--;
12     ll s=n,sum=n;
13     while (m){
14         if (m&1){
15             ans.push_back(Data{1,s,sum});
16             sum+=s;
17         }
18         ans.push_back(Data{1,s,s});
19         s<<=1,m>>=1;
20     }
21 }
22 void exgcd(ll a,ll b,ll &x,ll &y){
23     if (!b){
24         x=1,y=0;
25         return;
26     }
27     exgcd(b,a%b,y,x);
28     y-=(a/b)*x;
29 }
30 int main(){
31     scanf("%lld",&n);
32     ll t=2;
33     while ((t<<1)<=n)t<<=1;
34     calc(n,t);
35     m=((n*t)^n),ans.push_back(Data{0,n*t,n});
36     exgcd(n,m,x,y);
37     x=(x%m+m)%m;
38     if (x%2==0)x+=m;
39     y=(n*x-1)/m;
40     calc(n,x),calc(m,y);
41     ans.push_back(Data{0,n*x,m*y});
42     printf("%dn",(int)ans.size());
43     for(int i=0;i<ans.size();i++)
44         if (ans[i].p)printf("%lld + %lldn",ans[i].x,ans[i].y);
45         else printf("%lld ^ %lldn",ans[i].x,ans[i].y);
46     return 0;
47 }

View Code

 


程序员灯塔
转载请注明原文链接:[cf1427E]Xum
喜欢 (0)