清北集训Day3T1(转换)
这题可能是我与正解里的最近的一次了，可以还是sb的把正解叉了。
正解其实比较显然：因为f(x)只有81个取值，所以我们可以枚举f(x)，然后计算x，再判断x是否可以转化为f(x)
刚开始以为一个f(x)会对应很多x，所以这么枚举是错的。
但实际上我们在枚举f(x)的时候并不关注f(x)与x的关系，因此我们可以直接把f(x)看做与x毫不相关的变量y
这样枚举出y对应的x后再判断f(y)是否等于x，这样就一定是对的了
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int ans[MAXN],tot;
int f(int a,int p)
{
int base=0,ans=1;
while(a) base+=a%10,a/=10;
for(int i=1;i<=p;i++)
ans=ans*base;
return ans;
}
int a1[50]={10,0,1,2,3,4,5,6,7,8,9};
int a2[50]={3,0,1,81};
int a3[50]={7,0,1,512,4913,5832,17576,19683};
int a4[50]={7,0,1,2401,234256,390625,614656,1679616};
int a5[50]={6,0,1,17210368,52521875,60466176,205962976};
int main()
{
int T=read();
while(T--)
{
int a=read(),b=read(),c=read(),k=read();
if(a==1&&c==0)
{
tot=0;
//f(x)^a * b + c = x
k=min(k,(int)1e6);
for(int i=0;i<=k;i++)
if(f(i,a) * b + c == i)
ans[++tot]=i;
if(tot==0) {printf("0\n-1\n");continue;}
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
printf("%d ",ans[i]);puts("");
}
else if(b==1&&c==0)
{
if(a==1)
{
int ans=0;
for(int i=1;i<=a1[0];i++)
if(a1[i]<=k)
ans++;
if(ans==0) {printf("0\n-1\n");continue;}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d ",a1[i]);printf("\n");
}
else if(a==2)
{
int ans=0;
for(int i=1;i<=a2[0];i++)
if(a2[i]<=k)
ans++;
if(ans==0) {printf("0\n-1\n");continue;}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d ",a2[i]);printf("\n");
}
else if(a==3)
{
int ans=0;
for(int i=1;i<=a3[0];i++)
if(a3[i]<=k)
ans++;
if(ans==0) {printf("0\n-1\n");continue;}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d ",a3[i]);printf("\n");
}
else if(a==4)
{
int ans=0;
for(int i=1;i<=a4[0];i++)
if(a4[i]<=k)
ans++;
if(ans==0) {printf("0\n-1\n");continue;}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d ",a4[i]);printf("\n");
}
else if(a==5)
{
int ans=0;
for(int i=1;i<=a5[0];i++)
if(a5[i]<=k)
ans++;
if(ans==0) {printf("0\n-1\n");continue;}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d ",a5[i]);printf("\n");
}
}
else
{
tot=0;
//f(x)^a * b + c = x
for(int i=0;i<=k;i++)
if(f(i,a) * b + c == i)
ans[++tot]=i;
if(tot==0) {printf("0\n-1\n");continue;}
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
printf("%d ",ans[i]);puts("");
}
}
return 0;
}// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int MAXN=1e6+10;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
vector<int>v;
int check(int x)
{
int base=0;
while(x) base+=x%10,x/=10;
return base;
}
main()
{
int T=read();
while(T--)
{
int a=read(),b=read(),c=read(),k=read();
v.clear();
for(int i=0;i<=81;i++)
{
int x=i;
for(int j=1;j<a;j++) x=x*i;
x=x*b+c;
if(x<0||x>=k||check(x)!=i) continue;
v.push_back(x);
}
if(v.size()==0) {printf("0\n-1\n");continue;}
printf("%d\n",v.size());
for(int i=0;i<v.size();i++)
printf("%d ",v[i]);
printf("\n");
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-03-26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读