悠闲数学娱乐论坛(第2版)'s Archiver

realnumber 发表于 2019-8-23 18:48

各个位数上的数字都不相同的正整数

小明心中有一种美丽整数,这种数是指各个位数上的数字都不相同的正整数.
例如:12345是美丽整数,121就不是美丽整数.
a 是某正整数,问闭区间内[1,a]有几个美丽整数.
样例a=10,则有10个
a=1000,有738个.

青青子衿 发表于 2019-8-23 20:33

100以内,没有相同数码的正整数:[code]Select[Range[100],
FromDigits[DeleteDuplicates[IntegerDigits[#]]] == # &][/code]10000以内,没有相同数码的完全平方数:[code]Select[Range[100],
  FromDigits[DeleteDuplicates[IntegerDigits[#^2]]] == #^2 &]^2[/code]

kuing 发表于 2019-8-23 23:53

写出一个通式可能比较麻烦,但就具体的数来算还算容易,举个例:
[1,62485] 内的美丽整数中:
不超四位数的:9+9*9+9*9*8+9*9*8*7 个;
[1~5]xxxx 的:5*9*8*7*6 个;
6[0~1]xxx 的:2*8*7*6 个;
62[0~3]xx 的:3*7*6 个;
624[0~7]x 的:5*6 个;
6248[0~5] 的:4 个;
所以结果为:9 + 9*9 + 9*9*8 + 9*9*8*7 + 5*9*8*7*6 + 2*8*7*6 + 3*7*6 + 5*6 + 4 = 21226。

realnumber 发表于 2019-8-24 12:20

是的,通式要分很多类,暂时没找到好算法
小朋友编的,通过[code]#include<stdio.h>
using namespace std;

int h(int n,int m){
        int H=1;
        for(int i=0;i<m;i++,n--)H*=n;
        return H;
}

int g(int n){
        if(!n)return 0;
        int a[10],num=0,G=0;
        bool b[10]={1,1,1,1,1,1,1,1,1,1};
        while(n){
                num++;
                a[num]=n%10;
                n/=10;
        }
        for(int i=num;i>1;i--){
                for(int j=!(num-i);j<a[i];j++)if(b[j])G+=h(10-num+i-1,i-1);
                if(b[a[i]]){
                        b[a[i]]=0;
                }
                else return G;
        }
        for(int j=!(num-1);j<=a[1];j++)if(b[j])G++;
        return G;
}

int t(int n){
        int T=0;
        int num=0,sum=9;
        while(n>sum){
                num++;
                sum=sum*10+9;
                T+=9*h(9,num-1);
        }
        return T;
}

int f(int n){
        int F=0;
        F+=t(n);
        F+=g(n);
        return F;
}

int main(){
        int t;
        scanf("%d",&t);
        for(int i=0;i<t;i++){
                int l,r;
                scanf("%d%d",&l,&r);
                printf("%d\n",f(r)-f(l-1));
        }
        return 0;
}[/code]

kuing 发表于 2019-8-26 19:05

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=33479&ptid=6515]4#[/url] [i]realnumber[/i] [/b]

想了想其实写通式也不是很麻烦,也就两类情况。

求不超过 `\overline{a_1a_2\cdots a_n}`(`n\leqslant10`)的美丽整数个数。

记 `b_k` 为 `a_1` 至 `a_{k-1}` 当中小于 `a_k` 的个数(比如我在 3# 举的例子 `62485` 有 `b_2=0`, `b_3=1`, `b_4=3`, `b_5=2`)。

(1)若 `\overline{a_1a_2\cdots a_n}` 本身就是美丽整数,则所求个数为
\begin{align*}
&9(1+A_9^1+A_9^2+\cdots+A_9^{n-2})+(a_1-1)A_9^{n-1}\\
{}+{}&(a_2-b_2)A_8^{n-2}+(a_3-b_3)A_7^{n-3}+\cdots+(a_{n-1}-b_{n-1})A_{11-n}^1+a_n-b_n+1;
\end{align*}

(2)若 `\overline{a_1a_2\cdots a_n}` 不是美丽整数,设其在第 `m` 位首次出现重复数字(比如 `62685` 为 `m=3`),则所求个数为
\begin{align*}
&9(1+A_9^1+A_9^2+\cdots+A_9^{n-2})+(a_1-1)A_9^{n-1}\\
{}+{}&(a_2-b_2)A_8^{n-2}+(a_3-b_3)A_7^{n-3}+\cdots+(a_m-b_m)A_{10-m}^{n-m}.
\end{align*}

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.