集训2010-3-25 L.ppt

题目选讲
杭州二中赖陆航
Another Mathematical Problem
SPOJ AMATH
给定正整数n,k
求最小的正整数T,使得对任意正整数a,10k|(na+T-na),或判无解
n≤10100, k≤100
题目概述
n=32, k=2
T=4
10k|na(nT-1),不妨令a=1
令g=gcd(10k,n)
(10k/g)|((n/g)*(nT-1))
(10k/g)|(nT-1)
令m=10k/g,则gcd(10k/g,n)=1, T|φ(m)
设φ(m)=2A5B, T=2C5D
对任意T’=2C’5D’(C’≥C,D’≥D),m|(nT’-1)
分别从小到大枚举C,D,倍增计算nT
该算法时间复杂度为O((logn)2+k3)
分析
Island Explorer
SPOJ IEXPOLRE
题目概述
两条直线上分别分布着N,M个点
求这些点的Euclid最小生成树
N,M≤10000
分析
对于一条直线l1上的点A,设其投影到另一条直线l2上的相邻点为B,C
对l2上其余任一点D(不妨设D在C右方)
AD>AC,AD>CD
AD一定不在最小生成树上
跨直线的候选边只有AB,AC
最小生成树候选边共O(N+M)条
该算法时间复杂度为O((N+M)log(N+M))
A
B
C
D
k-th Product
SGU 421
给定n个整数a1,…,an
n个数取m个,在所有的N个m元组 b1,…,bN (N=C(n,m))中,求积第k大的
1≤n,k≤10000, 1≤m≤13, k≤C(n,m), -106≤ai≤106
题目概述
n=4, m=3, k=3, a=(2,3,3,5)
a2·a3·a4=45
a1·a2·a4=30
a1·a3·a4=30
a1·a2·a3=18
答案为30
假设a中没有负数。将a从大到小排序
由于k不大,不妨按顺序求出前k大解
称m元组b’=(al’1,al’2,…,al’m)是b=(al1,al2,…,alm)的前驱,当且仅当存在一个c,l’c=lc-1,且对所有i≠c,l’i=li类似的定义后继
若b已被求到,则b的所有前驱也已被求到
优先队列
每次取一个最大的m元组b
将b的后继全部插入优先队列
分析