首页 > 代码库 > CODEVS 2669 简单的试炼

CODEVS 2669 简单的试炼

2024-09-10 06:57:50   209人阅读

题目描述 Description

已知一个数S，求X和Y，使得2^X+3^Y=S.

输入描述 Input Description

(多组数据)

每行一个整数S，当S=0时输入结束.

输出描述 Output Description

X和Y，以2^X+3^Y=S的形式输出,若有多组解，输出X最小的那组.

样例输入 Sample Input

13

33

0

样例输出 Sample Output

2^2+3^2=13

2^5+3^0=33

数据范围及提示 Data Size & Hint

对于30%的数据  S≤50,000,000 , 数据组数≤5000

对于50%的数据  S≤3,000,000,000 , 数据组数≤20000

对于80%的数据  S≤3,000,000,000,000 , 数据组数≤50000

对于100%的数据 S≤200,000,000,000,000, 数据组数≤80000

 

暴力枚举 可以看出x最大为log2(s)那么 处理处x的范围 枚举可能的x 找对应的y在快速幂检验尽可以AC了
技术分享
 1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #define ll long long 5 using namespace std; 6 ll s; 7 inline void read(ll&x) { 8     x=0;ll f=1;char c=getchar(); 9     while(c>‘9‘||c<‘0‘) {if(c==‘-‘)f=-1; c=getchar();}10     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}11     x=x*f;12 }13 inline ll pow1(ll x,ll y)14 {15     ll base=1;16     while(y) {17         if(y&1) base=base*x;18         x=x*x;19         y>>=1;20     }21     return base;22 }23 int main() {24     while(scanf("%lld",&s)) {25           if(s==0) break;26           ll r,y;27         r=log2(s);28         for(int x=0;x<=r;x++) {29             y=log10(s-pow1(2,x))/log10(3);30             if(pow1(2,x)+pow1(3,y)==s) {31                 cout<<"2^"<<x<<"+3^"<<y<<"="<<s<<endl;32                 break;33             }34         }35     }36     return 0;37 }
代码

 

CODEVS 2669 简单的试炼


联系
我们