清北集训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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python入门

十五道Python小案例,学会这些,Python基础已过关!

分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。

61440
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

23840
来自专栏chenjx85的技术专栏

leetcode-70-Climbing Stairs

26890
来自专栏Python数据科学

如何用Python递归地思考问题?

递归是一个很经典的算法,在实际中应用广泛,也是面试中常常会提到的问题。本文就递归算法介绍如何在Python中实现递归的思想,以及递归在Python中使用时的一些...

88660
来自专栏专知

关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

34570
来自专栏斑斓

从map函数引发的讨论

只要你用心,一个细小问题可以引起对一系列设计原则的思考与回味。软件设计与开发技能就是这样通过不停“反刍”与思索而磨砺出来的。当然,对一些实践案例进行升华,进而抛...

39190
来自专栏web前端教室

=>,Es6箭头符号的前世今生

看代码能看错行,一看书就头疼且双眼流泪,没办法啊,都是娘胎里带出来的毛病,能看点是点吧。es6这种东西,虽然有一些语法糖,但毕竟也是新东西啊,得学。不学就落后,...

250100
来自专栏CSDN技术头条

关于设计模式的思考

为什么叫设计模式 什么是设计模式 设计模式最初是被 GoF 于1995年提出的。GoF 全称是Gang of Four(四人帮),即 Erich Gamma,R...

38060
来自专栏AzMark

Python字典的介绍

15220
来自专栏小樱的经验随笔

【Java学习笔记之二十二】解析接口在Java继承中的用法及实例分析

一、定义 Java接口(Interface),是一系列方法的声明,是一些方法特征的集合,一个接口只有方法的特征没有方法的实现,因此这些方法可以在不同的地方被不...

33550

扫码关注云+社区

领取腾讯云代金券