首页 > 代码库 > 编程之美2.8 | 找符合条件的整数
编程之美2.8 | 找符合条件的整数
思路还是相当地巧妙。
求余数的话，(a+b)%n=(a%n+b%n)%n;
用vector来表示整数的话（出现1的位置），可以避免溢出。
注意第20行，在更新remainders[(j+r)%n]时，要确保每个remainders的每个序列都是递增的，不能存在相等的情况。
1 #include <time.h> 2 #include <math.h> 3 #include <stdlib.h> 4 5 using namespace std; 6 7 long long findMInZeroOneNum(int n) { 8 vector<vector<int> > remainders(n); 9 remainders[1].push_back(0);10 11 bool update = false;12 int noupdate = 0;13 for (int i = 1, j = 10 % n; ; j = (j * 10) % n, i++) {14 if (remainders[j].empty()) {15 remainders[j].push_back(i);16 update = true;17 }18 for (int r = 1; r < n; ++r) {19 if (remainders[r].empty()) continue;20 if (i <= remainders[r].back()) continue;21 if (!remainders[(j + r) % n].empty()) continue;22 remainders[(j + r) % n] = remainders[r];23 remainders[(j + r) % n].push_back(i);24 update = true;25 }26 if (!update) noupdate++;27 else noupdate = 0;28 if (noupdate == n || !remainders[0].empty()) break;29 }30 31 if (remainders[0].empty()) return -1;32 else {33 long long ans = 0;34 for (int i = 0; i < remainders[0].size(); ++i) {35 ans += pow(10, remainders[0][i]);36 }37 return ans;38 }39 }40 41 long long bruteForce(int n) {42 if (n <= 0) return -1;43 for (long long i = 1; ; ++i) {44 if (i % n != 0) continue;45 long long tmp = i;46 while (tmp) {47 int d = tmp % 10; 48 if (d != 0 && d != 1) break;49 tmp /= 10;50 }51 if (tmp == 0) return i;52 }53 return -1;54 }55 56 int main() {57 srand(time(NULL));58 int n = rand() % 99;59 60 cout << n << endl;61 long long n1 = findMInZeroOneNum(n);62 cout << n1 << endl;63 long long n2 = bruteForce(n);64 cout << n2 << endl;65 if (n1 != n2) {66 cout << n << " " << n1 << " " << n2 << endl;67 }68 69 return 0;70 }
编程之美2.8 | 找符合条件的整数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。