首页 > 代码库 > UVA 11256 - Repetitive Multiple(数论)
UVA 11256 - Repetitive Multiple(数论)
UVA 11256 - Repetitive Multiple
题目链接
题意:找出一个最小值满足: 是n的倍数, 是重复数字(根据题目中的定义)
思路:如果是重复数字,形式必然是100010001这类形式乘上一个对应位数的数字,所以可以枚举这样形式的数字,和n取gcd,如果剩下的数字位数满足小于位数,那么就乘上一个数字使得等于最小满足位数,这样不断记录最小值即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long t, n, mi[10]; long long count(long long x) { long long ans = 0; while (x) { x /= 10; ans++; } return ans; } long long gcd(long long a, long long b) { while (b) { long long tmp = a % b; a = b; b = tmp; } return a; } int main() { mi[0] = 1; for (long long i = 1; i < 10; i++) mi[i] = mi[i - 1] * 10; scanf("%lld", &t); while (t--) { long long ans = 999999999999999999; scanf("%lld", &n); long long len = count(n); for (long long i = 1; i <= len; i++) { long long num = 1; for (long long j = i + i; j <= 2 * len; j += i) { num = num * mi[i] + 1; long long yu = n / gcd(num, n); if (count(yu) <= i) { long long tmp = mi[i - 1] / yu * yu; if (tmp < mi[i - 1]) tmp += yu; ans = min(ans, num * tmp); } } } printf("%lld\n", ans); } return 0; }
UVA 11256 - Repetitive Multiple(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。