首页 > 代码库 > uva 11256 - Repetitive Multiple(gcd+暴力)
uva 11256 - Repetitive Multiple(gcd+暴力)
题目链接:uva 11256 - Repetitive Multiple
题目大意:给定一个数n,要求找到最小的k,使得k?n为题目中定义的重复数字.
解题思路:枚举k?n的循环节长度,比如当前枚举为2,那么一次判断u=1001,1001001,1001001001 ...,取d = gcd(n,u), 那么k = u / d, a = n / d (因为n?k=u?a)并且保证a的长度为2,所以k和a要同时扩大相应倍数。枚举过程中为何k。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18+1;
ll N, ten[20];
void init () {
ten[0] = 1;
for (int i = 1; i < 20; i++)
ten[i] = ten[i-1] * 10;
}
inline ll gcd (ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
inline int tenbit (ll n) {
int cnt = 0;
while (n) {
n /= 10;
cnt++;
}
return cnt;
}
ll solve () {
ll ans = INF;
int bit = tenbit(N);
if (bit == 1)
return 11L;
for (int i = 1; i <= bit; i++) {
ll u = ten[i] + 1;
while (true) {
ll d = gcd(N, u);
ll a = N / d;
ll k = u / d;
if (a < ten[i]) {
if (a < ten[i-1])
a = ten[i-1] / a + (ten[i-1] % a ? 1 : 0);
else
a = 1;
if (a * k < ans)
ans = k * a;
}
if (INF / u < ten[i])
break;
u = u * ten[i] + 1;
}
}
return ans;
}
int main () {
init();
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%lld", &N);
while (N >= 1e9);
printf("%lld\n", solve() * N);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。