2017/04/19 两道水数论

Codeforces Round #409 Div.1 C. Vulnerable Kerbals

http://codeforces.com/contest/800/problem/C

题意:

构造一个尽可能长的序列,满足:

  • 每个数都在[0, m - 1]中。
  • 这个序列的前缀积互不相同。
  • 前缀积不能是被ban的n个数之一。

0 \leq n\textless m \le 200,000

最朴素的想法:假如a可以转移到b,则连一条边a->b,然后找最长路,然而边数太多而且有环。
然后我们发现,假如gcd(a, m) \mid gcd(b, m)则a能转移到b,于是我们把数字按gcd分类,然后就能建成一个DAG,然后dp找最长路即可:
dp[i] = max(dp[j] + cnt[i]), \{j \mid j->i\},cnt[i]gcd(x, m)==i的x的个数。
然后转移就用exgcd。

BZOJ 2818:Gcd

http://www.lydsy.com/JudgeOnline/problem.php?id=2818

题意:

给定整数N,求1 \leq x,y \leq Ngcd(x,y)为素数的数对(x,y)有多少对.

即求\sum_{p \in prime}\sum_{x=1}^{\lfloor N/p\rfloor }\sum_{y=1}^{\lfloor N/p\rfloor }[gcd(x, y)==1]
如果x \textless y,则与y互质的x\varphi (y)个,注意还要算上x==y的情况,所以最终的答案就是\sum_{p \in prime}(1+2*\sum_{x=1}^{\lfloor N/p\rfloor }\varphi(x))
算一下欧拉函数的前缀和即可。

发表评论