给定 N ，问是否存在正整数 A,B ，满足 3的A次方+5的B次方=N 。若存在，请输出字典序最小的解（在 A 最小的前提下 B 尽量小），若不存在，请输出 −1 。

这是一个经典的数学和计算机科学问题，通常被称为“中国剩余定理”（Chinese Remainder Theorem）的应用。不过这里的问题要求找到满足条件的最小解（A 最小且 B 尽量小），而不是一般意义上的最小公倍数。

要解决这个问题，我们需要遍历所有可能的 \(A\) 值，然后对于每个 \(A\)，计算对应的 \(B\) 的值。这个 \(B\) 的值可以通过模运算来快速求解。如果找到满足 \(3^A \equiv -N \mod 5\) 和 \(5^B \equiv -N \mod 3\) 的 \(A\) 和 \(B\)，则说明找到了一组解。

由于 \(3\) 和 \(5\) 是互质的（最大公约数为 1），我们可以单独处理对每个素数的同余方程。我们从最小的 \(A = 0\) 开始，逐步增加，直到找到一个使得 \(3^A \equiv -N \mod 5\) 成立的 \(A\)。接着，使用扩展欧几里得算法或直接计算 \(B\) 的值，使得 \(5^B \equiv -N \mod 3\)。

以下是一个简单的 C++ 代码示例，用于查找这样的解：

#include <iostream>
#include <vector>
using namespace std;

// 计算 x 对 y 取模的逆元，如果没有逆元返回 false
bool extendedEuclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return true;
    }
    bool res = extendedEuclidean(b, a % b, y, x);
    y -= a / b * x;
    return res;
}

int findSolutions(int N) {
    for (int A = 0; ; A++) { // 遍历 A
        int A_mod_5 = pow(3, A, 5); // 3^A mod 5
        if (A_mod_5 == -1 || A_mod_5 == 4) { // 找到 3^A ≡ -1 或 4 (mod 5)
            break;
        }

        int inv_A_mod_5 = -1; // 存储 A 对 5 的逆元
        if (!extendedEuclidean(5, A_mod_5, inv_A_mod_5, 0)) {
            continue;
        }
        int B = (inv_A_mod_5 * (N + 1)) % 5; // 计算 B

        int B_mod_3 = pow(5, B, 3); // 5^B mod 3
        if (B_mod_3 == 2 || B_mod_3 == 1) { // 找到 5^B ≡ 2 或 1 (mod 3)
            return A * 5 + B;
        }
    }

    return -1; // 如果找不到解，返回 -1
}

int main() {
    int N;
    cin >> N;
    int solution = findSolutions(N);
    cout << (solution == -1 ? "-1" : to_string(solution));
    return 0;
}