题意大概就是给你一个数,找到它可以由哪些3的倍数的数经过或运算得到,打印最少的个数好相应的解
首先要进行或运算,当然是把数字改写成二进制找规律,然后发现:
1、对于本身就是3的倍数的数,直接输出本身即可,不必考虑;
2、对于只有一位或者两位的值为一的数,无法用3的倍数来拼,不必考虑;
3、若把最低位当做第零位,则对于位数为奇数的1,即2^k%3恒等于2(k=2*n+1,n属于z),对于位数为偶数的1,即2^k%3恒等于1(k=2*n,n属于z),证明如下:
已知2^0=1,1%3=1,则2^0=3k+1,2^1=3k*2+1*2=6k+2,(6k+2)%3=2;如此反复,可以证明。
这个规律有什么用呢?
当然有用,我们可以把二进制的数当做每个为一的位数相加,例如1010=2^3+2^1,这样可以由以上规律可以得到它是不是3的倍数;
那么我们就可以用贪心的思想,对这个数的二进制数,我们找到他第一个为奇数的位数和第一个为偶数的位数,这样两个位数相加一定为3的倍数(对于只有奇数或者只有偶数的参加方法2)
那么我们就可以用剩下的1来拼凑出另外一个数,如果另外一个数不是三的倍数,我们可以通过借第一个数的奇1或者偶1来达成目的(反正或运算两个都是1或了还是1);
2、特殊情况:对于没有奇数或者偶数1的二进制数我们可以考虑用三个奇数1或者偶数1来拼凑出3 的倍数,然后仍旧是借1来使第二个数拼凑成3 的倍数。
下面上代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
#include<vector>
using namespace std;
#define ll long long
#define maxn 200005
ll fen(ll k){
    ll s=1,x=2;
    if(k==0)
        return 1ll;
    while(k>1){
        if(k%2)
            s*=x;
        x*=x;
        k/=2;
    }
    return s*x;
}
ll n,m,k,t;
ll num1,num2,sum;
bool a[100];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&k);
        if(k%3==0||k==1){
            printf("1 %lld\n",k);
            continue;
        }
        m=k;
        ll z=-1;
        num1=num2=-1;
        sum=0;
        while(k){
            z++;
            if(z%2==0&&k%2==1&&num1==-1)
                num1=z;
            if(z%2==1&&k%2==1&&num2==-1)
                num2=z;
            if(num1!=-1&&num2!=-1)
                break;
            a[z]=k&1;
            k/=2;
            sum+=a[z];
        }
        if(num1==-1||num2==-1){
            int z1=-1,z2=-1,z3=-1;
            for(int i=0;i<=z;i++){
                if(a[i]==1){
                    if(z1==-1)
                        z1=i;
                    else if(z2==-1)
                        z2=i;
                    else if(z3==-1){
                        z3=i;
                        break;
                    }
                }
            }
            ll ans1=fen(z1)+fen(z2)+fen(z3);
            ll ans2=m-ans1;
            if(sum%3==1)
                ans2+=(fen(z1)+fen(z2));
            else
                ans2+=fen(z1);
            printf("2 %lld %lld\n",ans1,ans2);
            continue;
        }
        ll ans1=fen(num1)+fen(num2);
        ll ans2=m-ans1;
        if(m%3==1)
            ans2+=fen(num2);
        else
            ans2+=fen(num1);
        printf("2 %lld %lld\n",ans1,ans2);
    }
}