7-1 Forever (20 分)

本文主要是介绍7-1 Forever (20 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考查的知识点：
1.暴力会超时，需要剪枝
2.输出不唯一时，先按照n排序，再按照A排序
3.没有的时候输出No Solution

#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm> 
#include <vector>
#include <cmath> 
#include <string> 
using namespace std; 
vector<pair<int, int>> vt;
int p[100]={0};
bool tag;
void prime(){for(int i = 2; i < 100; i++){if(!p[i]){for(int j = i+i; j < 100; j+=i){p[j] = 1; } } } 
} 
int gcd(int a, int b){return b == 0? a: gcd(b, a%b); 
} 
void dfs(int k, int u, int m, int sum, int xx){if(k == u){if(sum == m){int tmp = xx + 1;int n = 0; while(tmp){n += tmp%10;tmp /= 10; } int t = gcd(m, n); if(!p[t] && t > 2) {vt.push_back({n, xx});tag = true;}}return;}if(sum + (k - u)*9 < m ) return;for(int i = 0; i <= 9; i++ ){if(u==0&&i==0) continue;dfs(k, u+1, m, sum + i, xx*10 + i);}
}
int main(){ int n, k, m;string str, s; cin>>n; prime(); for(int i = 1; i <= n; i++){printf("Case %d\n", i);tag = false;cin>>k>>m;vt.clear();dfs(k, 0, m, 0, 0); sort(vt.begin(), vt.end());for(auto x: vt){cout<<x.first<<" "<<x.second<<endl;}if(!tag) cout<<"No Solution"<<endl;} return 0; 
} 

这篇关于7-1 Forever (20 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---