rockdu
题目描述
We consider the distance between positive integers in this problem, defined as follows.
A single operation consists in either multiplying a given number by a prime number1 or dividing it by a prime number (if it does divide without a remainder).
The distance between the numbers and
, denoted
, is the minimum number of operations it takes to transform the number
into the number
.
For example, .
Observe that the function is indeed a distance function - for any positive integers
,
and
the following hold:
the distance between a number and itself is 0: , the distance from
to
is the same as from
to
:
, and the triangle inequality holds:
.
A sequence of positive integers,
, is given.
For each number we have to determine
such that
and
is minimal.
给你一个序列a[]，定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数)，让a[i]=a[j]的最少操作步数
对于每个i，求d(i,j)最小的j，若有多个解，输出最小的j
输入输出格式
输入格式：
In the first line of standard input there is a single integer (
).
In the following lines the numbers
(
) are given, one per line.
In tests worth 30% of total point it additionally holds that .
输出格式：
Your program should print exactly lines to the standard output, a single integer in each line.
The -th line should give the minimum
such that:
,
and
is minimal.
输入输出样例
说明
给你一个序列a[]，定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数)，让a[i]=a[j]的最少操作步数
对于每个i，求d(i,j)最小的j，若有多个解，输出最小的j
我们从两个数的gcd考虑。我们先对值域内每一个数计算它作为GCD时，在给定的a数组中得到答案的最优值和次优值（包括距离和编号大小）。这步操作可以把a数组放进桶里进行容斥实现。然后我们再进行一步计数——对于每一个数作为GCD，它都对它的倍数有贡献。所以我们直接再一遍统计贡献就可以得到值域范围内每一个数的答案了（当然也包括a数组中的数了）。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5, inf = 0x3f3f3f3f;
int n, pos[maxn], a[maxn], tot[maxn], ord[maxn][2], N = 1e6;
int pri[maxn], vis[maxn], fac[maxn], mn[maxn], ans[maxn], num[maxn], Min = inf;
int pans[maxn];
int ans1 = inf, ans1p;
void GPri(int n) {
vis[1] = 1;
for(register int i = 2; i <= n; ++i) {
if(!vis[i]) pri[++pri[0]] = i, fac[i] = 1;
for(register int j = 1; j <= pri[0] && i * pri[j] <= n; ++j) {
vis[i * pri[j]] = 1, fac[i * pri[j]] = fac[i] + 1;
if(i % pri[j] == 0) break;
}
}
}
int Gpos(int a, int i) {
return ord[a][0] == i ? ord[a][1] : ord[a][0];
}
int main() {
scanf("%d", &n), GPri(N);
memset(ans, 0x3f, sizeof(ans));
memset(pans, 0x3f, sizeof(pans));
for(register int i = 1; i <= n; ++i) {
scanf("%d", &a[i]), ++tot[a[i]];
if(ans1 > fac[a[i]] && a[i] != 1)
ans1 = fac[a[i]], ans1p = a[i];
if(!ord[a[i]][0]) ord[a[i]][0] = i;
else if(!ord[a[i]][1]) ord[a[i]][1] = i;
}
for(register int i = 1; i <= N; ++i)
for(register int j = 1; j * i <= N; ++j)
if(tot[j * i]) if(pans[i] > fac[i] + fac[j]) pans[i] = fac[i] + fac[j], mn[i] = i * j;
else if(pans[i] == fac[i] + fac[j] && ord[i * j][0] < ord[mn[i]][0]) mn[i] = i * j;
for(register int i = 1; i <= N; ++i)
for(register int j = 1; j * i <= N; ++j) {
if(mn[i] == i * j && tot[i * j] == 1) continue;
if(!mn[i]) continue;
if(ans[i * j] > (fac[mn[i] / i] + fac[j]))
ans[i * j] = (fac[mn[i] / i] + fac[j]), num[i * j] = mn[i];
else if(ans[i * j] == (fac[mn[i] / i] + fac[j]) && Gpos(mn[i], -1) < Gpos(num[i * j], -1))
ans[i * j] = (fac[mn[i] / i] + fac[j]), num[i * j] = mn[i];
if(tot[i * j] && ans[mn[i]] > (fac[mn[i] / i] + fac[j]))
ans[mn[i]] = (fac[mn[i] / i] + fac[j]), num[mn[i]] = i * j;
else
if(tot[i * j] && ans[mn[i]] == (fac[mn[i] / i] + fac[j]) && Gpos(i * j, -1) < Gpos(num[mn[i]], -1))
ans[mn[i]] = (fac[mn[i] / i] + fac[j]), num[mn[i]] = i * j;
}
if(!num[1]) num[1] = ans1p;
for(register int i = 1; i <= n; ++i)
printf("%d\n", Gpos(num[a[i]], i));
return 0;
}
没有帐号? 立即注册