G - Eva's Balance (3进制&数论）

题意：给个的幂次方数：和一个数，要求用这个数中若干个使左右两个秤盘数之和相等.
（开始被放在左盘）

思路：因为都是的幂次方,题目等价于构造两个的幂次方之和相减等于,所以考虑进制下来表示.

所以被转化为的数字串。当该位为时,显然可以不会用到或者直接抵消掉。

当时,因为。所以等价于然后。

当时,显然，所以等价于.然后再根据的正负情况，将负的给左盘，正的给右盘，此题就解决了。

时间复杂度：

AC代码:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e3+5,inf=0x3f3f3f3f;
int a[N],n,t;
#define mst(a) memset(a,0,sizeof a)
int ksm(int a,int n){ //快速幂板子. 
    int ans=1;
    while(n){
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        mst(a);
        int k=0;
        while(n){ //转换为三进制. 
            a[++k]=n%3;
            n/=3;
        }
        int f1=0,f2=0;//用来控制格式(逗号) 
        for(int i=1;i<=k+1;i++){ //重点转换. 
            if(a[i]==2) a[i]=-1,a[i+1]++;
            else if(a[i]==3) a[i]=0,a[i+1]++;
        }
        for(int i=1;i<=k+1;i++){ //输出 注意是可能k+1位. 
            if(a[i]==-1){
                if(f1) printf(",%d",ksm(3,i-1));
                else f1=1,printf("%d",ksm(3,i-1));
            }
        }
        if(!f1) printf("empty");
        printf(" ");
        for(int i=1;i<=k+1;i++){
            if(a[i]==1){
                if(f2) printf(",%d",ksm(3,i-1));
                else f2=1,printf("%d",ksm(3,i-1));
            }
        }
        if(!f2) printf(" empty");
        puts("");
    }
    return 0;
}