「CF516A」Drazil and Factorial
题解
定义函数F(a) 为a的数位阶乘乘积。例如 F(135) = 1! * 3! * 5! 。求 max{x},F(x) = F(a),且组成 x 的数字中没有0和1
质因数分解以后按素数贪心即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n; int fac[25],t[10]; char ch[25]; void solve(int num,int val) { for(int x=2;x*x<=num;x++) { while(num%x==0)num/=x,t[x]+=val; } if(num>1)t[num]+=val; } int main() { fac[1]=1; for(int i=2;i<=9;i++)fac[i]=fac[i-1]*i; n=read(); scanf("%s",ch+1); for(int i=1;i<=n;i++) solve(fac[ch[i]-'0'],1); while(t[7]!=0)solve(fac[7],-1),printf("7"); while(t[5]!=0)solve(fac[5],-1),printf("5"); while(t[3]!=0)solve(fac[3],-1),printf("3"); while(t[2]!=0)solve(fac[2],-1),printf("2"); return 0; } |
Subscribe