2019牛客暑期多校训练营（第四场）D triples I（构造+思维）
链接：https://ac.nowcoder.com/acm/contest/884/D
题意：T组样例。每组样例给出一个a（1<=a<=1e18），让用尽可能少的3的倍数，使这些数按位或起来的值为a。题目保证输入的a一定有答案。
思路：既然是按位或，那么肯定和二进制有关。显然，一个数的二进制中，奇数位上的1%3=1，偶数位上的1%3=2。那么我们就统计奇数位，偶数位上的个数并用数组记下。首先，我们最多用2个数肯定能凑出这个数。然后分类讨论。
1.a%3==0，显然就是只用a这一个数即可，否则肯定要用两个数。
2.a%3==1，我们就要想办法删去这个1。再次分类讨论：
（1）奇数位上的1和偶数位上的1都不为0，那么我们只需删去第一个奇数位上的1构造出第一个数（这个数肯定是3的倍数），然后再用上删去的那个数和第一个偶数位上的数构造出第二个数（(1+2)%3==0,也肯定是3的倍数）。
（2）奇数位上的1不为0，偶数位上的1为0。那么我们也是只需删去第一个奇数位上的1构造出第一个数，再用上删去的那个数和其后的前2个奇数位的数（也就是用前三个奇数位上的数，（1+1+1）%3==0，是3的倍数）。
（3）奇数位上的1为0，偶数位上的1不为0。那么我们只需删去前两个偶数位上的数构造出第一个数（(2+2)%3==1,删去后肯定是3的倍数），再用上删去的那两个数和其后的第一个偶数位的数（也就是用前三个偶数位上的数，（2+2+2）%3==0，是3的倍数）。
3.a%3==2,同理，我们要想办法删去这个2。再次分类讨论：
（1）奇数位上的1和偶数位上的1都不为0，那么我们只需删去第一个偶数位上的1构造出第一个数（这个数肯定是3的倍数），然后再用上删去的那个数和第一个奇数位上的数构造出第二个数（(1+2)%3==0,也肯定是3的倍数）。
（2）奇数位上的1为0，偶数位上的1不为0。那么我们也是只需删去第一个偶数位上的1构造出第一个数，再用上删去的那个数和其后的前2个偶数位的数（也就是用前三个偶数位上的数，（2+2+2）%3==0，是3的倍数）。
（3）奇数位上的1不为0，偶数位上的1为0。那么我们只需删去前两个奇数位上的数构造出第一个数（(1+1)%3==2,删去后肯定是3的倍数），再用上删去的那两个数和其后的第一个奇数位的数（也就是用前三个奇数位上的数，（1+1+1）%3==0，是3的倍数）。
注意：一定要用上删去的那若干个数，不然构造出两个数按位或后就不等于a。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,ans1,ans2,odd[65],even[65],cnto,cnte;
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
cnto=cnte=0;
scanf("%lld",&a);
if(a%3==0)
{
printf("1 %lld\n",a);
continue;
}
for(int i=0;i<=60;i++)
{
if(a&(1LL<<i))
{
//这里要(i+1)，因为从0开始的
if((i+1)&1) odd[++cnto]=(1LL<<i);
else even[++cnte]=(1LL<<i);
}
}
//分类讨论
if(a%3==1)
{
if(cnto!=0&&cnte!=0)
{
ans1=odd[1]+even[1];
ans2=a-odd[1];
}
else if(cnto!=0)
{
ans1=odd[1]+odd[2]+odd[3];
ans2=a-odd[1];
}
else
{
ans1=even[1]+even[2]+even[3];
ans2=a-even[1]-even[2];
}
}
else
{
if(cnto!=0&&cnte!=0)
{
ans1=odd[1]+even[1];
ans2=a-even[1];
}
else if(cnto!=0)
{
ans1=odd[1]+odd[2]+odd[3];
ans2=a-odd[1]-odd[2];
}
else
{
ans1=even[1]+even[2]+even[3];
ans2=a-even[1];
}
}
//cout<<(ans1|ans2)<<endl;
printf("2 %lld %lld\n",ans1,ans2);
}
return 0;
}