我想把十进制数转换成阶乘数。
我想这样做是为了找到最多100个元素的数组的第n个字典置换排列,例如A(87)={1,2,3,…,87 }。
我得到了索引“n”,它的词典编排在那个位置我需要找到。例如,{1,2,3}的第二置换是{1,3,2}
为此,我尝试使用阶乘数系统。
下面的链接提供有关转换方法的信息。
https://en.wikipedia.org/wiki/Factorial_number_system
如所解释的(463)十进制给出341010在阶乘中。
463÷1=463,余数0
463÷2=231,余数1
231÷3=77,余数0
77÷4=19,余数1
19÷5=3,余数4
3÷6=0,余数3
只有当十进制数在允许的范围内(如无符号长整型整数)时,才能应用此方法。
如果数字不在整数范围内怎么办?
我的测试用例包含的数字太大,需要以字符串格式存储(例如,查找12345678901234567890123456789012355623344数组排列[100]={1,2,3,4,….100})
我试图用c++来解决这个问题。
(使用C++中的next_permutation()来获得给定的索引是一种代价高昂的方法,需要花费大量时间。)

最佳答案

这是密码你可以看到并问我是否有任何困惑。
另外,我只有一个测试用例,你已经提供,我没有做一个详尽的代码测试如果你发现任何错误,我很乐意解决。

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000000
#define MOD 1000000007
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define V vector
#define I int
#define D double
#define B bool
#define pii pair<int,int>
#define LL long long

#define in(x) scanf("%d",&x)
#define in2(x,y) scanf("%d%d",&x,&y)
#define lin(x) scanf("%lld",&x)
#define lin2(x,y) scanf("%lld%lld",&x,&y)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define all(v) v.begin(),v.end()

string q;    //this is the input
V<I> sol;    //this is final solution vector. (will be printed in reverse)

void divide(I n){    //function to divide a string by `n`
    string r = "";
    I i,k=0;
    FOR(i,0,q.length()){
        k *= 10;
        k += (q[i] - '0');
        I g = k / n;
        k = k % n;
        if((r.length()==0 && g!=0) || (r.length()>0)){
            r += (char)(g + '0');
        }
    }
    q = r;
    sol.PB(k);
}

I main(){
    cin>>q;
    I i;
    FOR(i,1,101){   //assuming 100 is the limit
        if(q.length()==0)
            break;
        divide(i);
    }
    //print the result
    for(i=sol.size()-1;i>=0;i--)
        //printf("%d ",sol[i]);
        cout<<sol[i]<<" ";
    printf("\n");
    return 0;
}

10-04 20:57