I'm asking this question because there's a part where I'm stuck while solving Baekjun's https://www.acmicpc.net/problem/12779( issue original) It's a problem where the numerator is the square number within a given range and the denominator is within a given range It's normal up to here There's a phrase that says to express it in the form of a "promising fraction." We added a function that divides the numerator and denominator by each maximum number of pledges I would appreciate it if you could tell me where the problem is because the wrong value is printed.
//
#include <iostream>
#include <cmath>
using namespace std;
unsigned int findpow(unsigned int m);
unsigned int gcd(unsigned int q, unsigned int p);
int main(){
unsigned inta, b;//0~(the power of 2 to 30)
cin >> a >> b;
if (findpow(b) - findpow(a) == 0) { cout << '0'; }
else {
cout << (findpow(b) - findpow(a))/gcd(findpow(b), findpow(a)) << '/' << (b - a)/gcd(findpow(b), findpow(a));
}return 0;
}
unsigned int findpow(unsigned int m) {//to get a square number
for (int i = 1; i < pow(2, 30); i++) {
if (m < pow(i, 2)) {
break;
}return (i - 1);
}
}
unsigned int gcd(unsigned int q, unsigned int p) {
unsigned int k = 0;
while (p != 0){
k = q % p;
q = p;
p = k;
}
return p;
}
unsigned int gcd(q, p) wins. while If you're looking for the maximum number of pledges through an infinite loop, you can roughly do it like this (I don't know C, so I only explain the algorithm with Python.)
def gcd(a, b) :
# We will select candidates for the common divisor.
# If you are lucky, you can divide the larger number by the smaller number of the two, so you first pick him as a candidate.
c = a if a < b else b
# Now, let's modulate the two numbers with the common divisor candidate.
while a % c != 0 or b % c != 0 :
# If either of the two is not separated, subtract 1 from the current candidate and try it again.
c = c - 1
# If both have been divided, candidate Gong Myung-soo is actually the biggest pledge.
return c
# Hey! You can get the biggest pledge, too!
print(gcd(7, 3))
print(gcd(24, 18))
print(gcd(16*17, 12*17))
I hope it helps.
I will transfer your code to C.
unsigned int gcd(unsigned int a, unsigned int b) {
int c = a < b ? a : b;
while((a % c != 0) || (b % c != 0)) { c -= 1; }
return c;
}
I've been working on the rest of this and that.
[cling]$ .L main.cpp
[cling]$ main()
1/3
#include <iostream>
#include <cmath>
using namespace std;
unsigned int findpow(unsigned int m);
bool issquare(unsigned int n);
unsigned int gcd(unsigned int a, unsigned int b);
unsigned int findpow(unsigned int m) {
for (int i = 1; i < pow(2, 30); i++) {
if (m == pow(i, 2)) {
return i;
}
}
return 0;
}
// Determine the number of squares
bool issquare(unsigned int n) {
return pow(pow(n, 0.5), 2) == n;
}
unsigned int gcd(unsigned int a, unsigned int b) {
int c = a < b ? a : b;
while((a % c != 0) || (b % c != 0)) { c -= 1; }
return c;
}
int main() {
int a = 1, b = 4;
if(issquare(a) && issquare(b)) {
cout << int((findpow(b) - findpow(a))/gcd(findpow(b), findpow(a))) << "/" << int((b - a)/gcd(findpow(b), findpow(a))) << endl;
}else{
cout << '0' <<endl;
}
return 0;
}
unsigned int findpower(unsigned int) {// To calculate the square number
for (int i = 1; i < pow(2, 30); i++) {
if (m < pow(i, 2)) {
break;
}
}
return (i - 1);
}
And, in order to divide the components, you have to divide them by the common divisors of the numerator and the denominator, and you're dividing them by the odd common divisors.
© 2024 OneMinuteCode. All rights reserved.