算法-每天一道题（14）-求一个数的最大公约数-最简分式

求最大公约数

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
	int t;
        // 思路：a中可以拆分成多个b和1个t，多个b不需要管
	while (b != 0)
	{
		t = a%b;
		a = b;
		b = t;
	}
	return a;
}

int main()
{
	int a1, a2;
	cin >> a1 >> a2;
	int a = (a1 > a2 ? gcd(a1, a2) : gcd(a2, a1));
	cout << a << endl;
	char c;
	cin >> c;
	return 0;
}

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    void getNum(int num) {
        int count = 0;
        for (int i = 2; i<num; i++) {
            vector<int> v;
            this->putVector(v, num, i);
            count += this->getCount(v);
            v.clear();
        }
        int b = num - 2;
        int Y;// 最大公约数

        while (true) {
            Y = (count > b ? this->gcd(count, b) : this->gcd(b, count));
            if (Y == 1)
                break;
            count = count / Y;
            b = b / Y;
        }
        cout << count << "/" << b << endl;
    }

    int gcd(int a, int b)
    {
        int t;
        while (b != 0)
        {
            t = a%b;
            a = b;
            b = t;
        }
        return a;
    }

    int getCount(vector<int> &v) {
        int count = 0;
        for (int i = 0; i<v.size(); i++)
            count = count + v[i];
        return count;
    }

    void putVector(vector<int> &banary, int num, int le) {
        while (true) {
            if (num < le) {
                banary.push_back(num);
                break;
            }
            banary.push_back(num%le);
            num = num / le;
        }
    }
};

int main(int argc, char const *argv[])
{
    Solution a;
    int num;
    while (cin >> num)
        a.getNum(num);
    return 0;
}