P2821 变幻数 题解

CSDN同步

原题链接

简要题意:

一个数把各位数字乘起来得到另一个数。已知另一个数,求最小的“一个数”。

首先,你发现,假设答案为 (m) ,给定 (n) ,那么此时 (m) 的各位数字之积为 (n).

既然已知 (n),那么我们就应该分解 (n).

比方说,(18 = 2 imes 9),那么答案就是 (29).

再比方说,(250 = 2 imes 5^3),那么答案就是 (2555).

那么,无解情况是什么?

比方说,(999 = 3^3 imes 37),此时需要有一个 (37),但是 (37) 是两位数,所以不合法。

因此。(n) 的质因子不能超过 (9). 否则不合法。

知道这些之后,我们只要从 (9)(2) 进行除法即可。(高精度除法其实挺简单的哦~)

那么你说了,怎么保证得到的答案一定比 (n) 大呢?

假设存在答案。那么 (n) 每分解一个 (leq 9) 的数就会在原来的答案拼上一位,那么原来的答案至少也是 ( imes 10).

那么也就是说,(n) 每次会除掉 (2) ~ (9),但答案会 ( imes 10). 所以答案肯定比 (n) 大。证毕。

时间复杂度:(O( operatorname{size}_n ))

实际得分:(100pts).

这也叫蓝题???

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int main(){
	string s; cin>>s;
	vector<int>v; int l=0;
	int x=9; while(x>=2) {
		int sum=0;
		for(int i=0;i<s.size();i++) sum=(sum*10+s[i]-'0')%x; //试除
		if(!sum) { //能整除
			v.push_back(x);
			for(int i=0;i<s.size();i++) {
				sum=sum*10+s[i]-'0';
				s[i]=sum/x+'0'; sum%=x; //除掉
			} l=(s[l]=='0')?(++l):l; //l 表示,除完一次之后被砍掉的位数
		} else x--;
	} if(l!=s.size()-1) puts("There is no such number!");
        //如有解,那么 2~9 的质因子就应该把 n 变成 1,即全部砍掉。否则说明无解。
	else {
		reverse(v.begin(),v.end()); //我们是从大到小除的,翻转
		for(int i=0;i<v.size();i++) printf("%d",v[i]);
		putchar('
');
	}
	return 0;
}

原文地址:https://www.cnblogs.com/bifanwen/p/12597781.html