UVa 10190 - Divide, But Not Quite Conquer! 解法

題目：

Your goal in this problem is to divide a certain integer n by another integer m until n = 1, obtainingn> a sequence of numbers. Lets call a[i] each number of this sequence, and let’s say it has k numbers (i.e.n> you must do k − 1 succesive divisions to reach n = 1). You can only have this sequence if the followingn> restrictions are met:n> n> - a[1] = n, a[i] = a[i − 1] ÷ m, for all 1 < i ≤ kn> - a[i] is divisible by m (that is, a[i] mod m = 0) for all 1 ≤ i < kn> - a[1] > a[2] > a[3] > . . . > a[k]n> n> For instance, if n = 125 and m = 5, you have 125, 25, 5 and 1 (you did 3 divisions: 125/5, 25/5n> and 5/5). So, k = 4, a[1] = 125, a[2] = 25, a[3] = 5 and a[4] = 1.n> If n = 30 and m = 3, you have 30, 10, 3 and 1. But a[2] = 10, and 10 mod 3 = 1, so there is non> sequence because it violates restriction 2. When the sequence doesn’t exist we think it’s not fun and,n> thus, very boring!

暴力解

一直除法取餘數判斷整不整除

#include <iostream>
#include <string>
using namespace std;
bool isRightInput(long long n,long long m);
int main()
{
	long long n,m;
	while(cin >> n >> m){
		long long temp = n;
		string result = "";	
		if(IsRightInput(n,m)){
			while(temp > 1){
				result += to_string(temp) + " ";
				
				if(temp % m != 0){
					break;
				}
				
				temp /= m;
			}
			
			if(temp == 1){
				cout << result + "1" << endl;
			}else{
				cout << "Boring!" << endl;
			}
			
		}else{
			cout << "Boring!" << endl;
		}
	}
	
	return 0;
}

bool IsRightInput(long long n ,long long m){
	return n >= m && n > 1 && m > 1;
}

數學解 以m為底使用log計算n是m的幾次方，如果算出來不是整數，代表它是Boring!

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

bool IsRightInput(long long n, long long m);
bool IsIntegerOfPower(long long n, long long m);
int main()
{
	long long n, m;

	while (cin >> n >> m) {
		long long temp = n;
		string result = "";
		if (IsRightInput(n, m) && IsIntegerOfPower(n, m)) {
			while (temp > 1) {
				result += to_string(temp) + " ";
				temp /= m;n			}

			cout << result + "1" << endl;
		}
		else {
			cout << "Boring!" << endl;
		}
	}
}

bool IsRightInput(long long n, long long m) {
	return n >= m && n > 1 && m > 1;
}

bool IsIntegerOfPower(long long n, long long m) {
	double power = m == 10 ? log10(n) : log(n) / log(m);

	return (power - (int)power) < 0.000001;
}