首页 > 代码库 > Vijos 波浪数

Vijos 波浪数

描述

波浪数是在一对数字之间交替转换的数,如1212121,双重波浪数则是指在两种进制下都是波浪数的数,如十进制数191919是一个十进制下的波浪数,它对应的十一进制数121212也是一个波浪数,所以十进制数191919是一个双重波浪数。

类似的可以定义三重波浪数,三重波浪数在三种不同的进制中都是波浪数,甚至还有四重波浪数,如十进制300=606(七进制)=363(九进制)=454(八进制)=1A1(十三进制)…,你的任务就是在指定范围内找出双重、三重、四重波浪数。

格式

输入格式

单独一行包含五个用空格隔开的十进制整数,前两个数表示进制的范围(2..32),第三与第四个数表示指定的范围(1..10000000),第五个数为2,3,4中的一个,表示要找的波浪数的重数。

输出格式

从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。

样例1

样例输入1

10 11 190000 960000 2
Copy

样例输出1

191919383838575757767676959595
Copy

限制

每个测试点1s

来源

冰火熔寒&XTXWZOI

 

技术分享
 1 /* 2     如果从x到y循环的话 会超时的 3     那么就枚举进制 构造进制数 4     再找s重进制数  5 */ 6 #include<ctime> 7 #include<cstdio> 8 #include<iostream> 9 #define MAXN 1000001010 11 using namespace std;12 13 int ja,jb,x,y,s;14 15 int num[MAXN];16 17 inline void read(int&x) {18     x=0;int f=1;char c=getchar();19     while(c>9||c<0) {if(c==-) f=-1;c=getchar();}20     while(c>=0&&c<=9) {x=(x<<1)+(x<<3)+c-48;c=getchar();}21     x=x*f;22 }23 24 inline int query_long(int n,int p) {25     int cnt=0;26     while(n) {27         n/=p;28         cnt++;29     }30     return cnt;31 }32 33 inline int TEN_MAKE(int a,int b,int len,int p) {34     int NUM=0;35     for(int i=1;i<=len;i++) {36         if(i&1) NUM=NUM*p+a;37         else NUM=NUM*p+b;38     }39     return NUM;40 }41 42 inline void JZ_make(int p) {43     int l=query_long(x,p),r=query_long(y,p);44     for(int i=1;i<p;i++)45       for(int j=0;j<p;j++)46         if(i!=j) 47           for(int len=l;len<=r;len++) {48               int th=TEN_MAKE(i,j,len,p);49               if(th>=x&&th<=y) num[th]++;50           }51     return;52 }53 54 int main() {55     read(ja);read(jb);read(x);read(y);read(s);56     for(int i=ja;i<=jb;i++)57       JZ_make(i);58     for(int i=x;i<=y;i++)59       if(num[i]==s) printf("%d\n",i);60     return 0;61 }
代码

 

Vijos 波浪数