MoonNight

Jul 11, 2022

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

## CPE 2022/05/24 22D1.UVa10190

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;
}
``````

``````#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;
}
``````
500
2

2 則留言

bernie

2023-03-14 14:20:05