1104 天长地久更多...

函数
void	dfs (string str, const int current_i, const int m, const int k, const int current_sum, const int cnt9, vector< string > &ans)

bool	is_prime (int n)

int	main (istream &cin, ostream &cout)

	TEST (b1104, case1)

详细描述

1104 天长地久

函数说明

◆ dfs()

void pat::b::b1104::dfs	(	string	str,
		const int	current_i,
		const int	m,
		const int	k,
		const int	current_sum,
		const int	cnt9,
		vector< string > &	ans )

在文件 pat.cpp 第 3721 行定义.

                                                                                                                                            {
                if(current_i + cnt9 == k) {
                    if(const int r = m - current_sum - cnt9 * 9; (current_i > 1 && r >= 0 || current_i == 1 && r > 0) && r < 9) {
                        str += static_cast<char>(r + '0');
                    } else {
                        return;
                    }
                    for(int i = 0; i < cnt9; i++) {
                        str += '9';
                    }
                    ans.emplace_back(str);
                    return;
                }
                for(int i = current_i == 1 ? 1 : 0; i <= 9; i++) {
                    if(!(current_sum + i + cnt9 * 9 > m || current_sum + i + (k - current_i) * 9 - 1 < m)) {
                        dfs(str + static_cast<char>(i + '0'), current_i + 1, m, k, current_sum + i, cnt9, ans);
                    }
                }
            }

引用了 dfs().

被这些函数引用 dfs() , 以及 main().

◆ is_prime()

bool pat::b::b1104::is_prime ( int n )

在文件 pat.cpp 第 3709 行定义.

                                 {
                if(n == 1) {
                    return false;
                }
                for(int i = 2; i <= sqrt(n); i++) {
                    if(n % i == 0) {
                        return false;
                    }
                }
                return true;
            }

被这些函数引用 main().

◆ main()

int pat::b::b1104::main	(	istream &	cin,
		ostream &	cout )

在文件 pat.cpp 第 3675 行定义.

                                                  {
                int N;
                cin >> N;
                vector<int> diff(10);
                for(int i = 0; i < 10; i++) {
                    diff[i] = 1 - i * 9;
                }
                for(int i = 1; i <= N; i++) {
                    bool ok = false;
                    int k;
                    int m;
                    cin >> k >> m;
                    cout << "Case " << i << endl;
                    for(int j = k; j >= 1; j--) {
                        const int n = m + diff[j];
                        const int g = gcd(m, n);
                        if(n > 0 && g > 2 && is_prime(gcd(m, n))) {
                            vector<string> ans;
                            dfs("", 1, m, k, 0, j, ans);
                            if(!ans.empty()) {
                                ok = true;
                                for(const auto &str: ans) {
                                    cout << m + diff[j] << ' ' << str << endl;
                                }
                            }
                        }
                    }
                    if(!ok) {
                        cout << "No Solution" << endl;
                    }
                }
                return 0;
            }

引用了 dfs() , 以及 is_prime().

被这些函数引用 TEST().

◆ TEST()

pat::b::b1104::TEST	(	b1104	,
		case1	)

在文件 pat_test.cpp 第 1832 行定义.

                               {
                istringstream in("2\n"
                                 "6 45\n"
                                 "7 80");
                auto out = ostringstream();
                main(in, out);
                const auto ans = out.str();
                ASSERT_EQ("Case 1\n"
                          "10 189999\n"
                          "10 279999\n"
                          "10 369999\n"
                          "10 459999\n"
                          "10 549999\n"
                          "10 639999\n"
                          "10 729999\n"
                          "10 819999\n"
                          "10 909999\n"
                          "Case 2\n"
                          "No Solution\n",
                          out.str());
            }

引用了 main().