筛法真是数论中的好东西,可以预处理方便大规模查询,比如今天做的第K大公因子

Problem Description

友谊度$friend(a,b)$是这么计算的:令$a, b$ 两个整数分别是两个同学的属性,两个同学的友谊度取决于 $a,b$ 第$k$ 大的公约数。如果不存在,就说明这两个同学之间完全没有友谊,友谊度为 $−1$。

Input

第一行是数据组数 $T (1≤T≤60)$。
对于每组数据:
第一行:首先是学生的数量 $n (1≤n≤10^5)$,约定的常数 $k (1≤k≤10^6)$。
第二行:$n$个整数,依次表示这些学生的属性值:$m_1,m_2,…,m_n (1≤m_i≤10^6)$。

Output

对于每组数据输出一行,以 Case x: 开头(x 表示数据编号,从 1 开始),后面是 n−1 个整数,分别是$friend(m_1,m_2),friend(m_2,m_3),…,friend(m_n−1,m_n)$,整数和整数之间用空格隔开。

Sample input

[cpp]
2
3 1
4 6 12
6 2
13 12 12 24 36 30[/cpp]

Sample output

[cpp]
Case 1: 2 6
Case 2: -1 6 6 6 3[/cpp]

Source 2017华东师范大学校赛K题

[cpp]
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
vector <int>V[maxn];
int value[maxn];
int main() {
for(int i=0; i<maxn; i++) V[i].clear();
for(int i=1; i<maxn; i++)
for(int j=i; j<maxn; j+=i) V[j].push_back(i);
int t; scanf(“%d”,&t);
for(int kase=1; kase<=t; kase++) {
int n,k;
scanf(“%d %d”,&n, &k);
for(int i=1; i<=n; i++)
scanf(“%d”, &value[i]);
printf(“Case %d:”,kase);
for(int i=2;i<=n;i++) {
int gcd=__gcd(value[i-1],value[i]);
int pos=V[gcd].size();
if(pos<k) printf(” -1″);
else printf(” %d”,V[gcd][pos-k]);
}
puts(“”);
}
}[/cpp]

分类: ACM数论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.