传送门

已知 $a,b,X_1,p,t$ ,

给定递推公式 $X_{i+1}=(aX{i}+b)\mod p(i\ge 1)$ ,求最小的正整数i满足 $X_i=t$ ,p为质数。

BZOJ 2242 计算器

你被要求设计一个计算器完成以下三项任务:

  1. 给定y,z,p,计算$y^z\mod p$ 的值;
  2. 给定y,z,p,计算满足$xy \equiv z(\mod p)$的最小非负整数;
  3. 给定y,z,p,计算满足$y^x \equiv z (\mod p)$的最小非负整数。

其中p为质数,$y,z,p\le 10^9$

传送门

简要题意:将一棵树上的一些节点染成黑色,使每个叶子节点到根节点的黑色节点数和相等。最大化黑色节点数。

Task1: 30pts $n\le 20$

Task2: 30pts $n\le 1000$

Task3: 40pts $n\le 100000$

ARC084B Small Multiple

求k的倍数中数位和的最小值。

原根(半转载)

原根定义:

设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)(from 51nod)

原根要求

k有原根当且仅当$k=2,4,p^a,2p^a$
其中p是奇素数,a是正整数

如何找模k的最小原根:

暴力枚举判断是不是满足条件。

判断算法:

(首先保证$\gcd(a,m)=1$)

暴力

假设要判断的数为s,判断2到$\phi(k)-1$中是否有一个正整数t满足$s^t\equiv 1(\mod k)$,如果有则不是,否则就是。
时间复杂度$O(\phi(k))$,其实就是$O(k)$

更快速的方法

设$x=\phi(k)$,对于每个x的素因数p判断$s^{\frac{x}{p}}\mod k$是否为1。如果是则s不是原根。如果都不是则s是原根。

感性理解吧。

概述

对于求最长回文子串的暴力算法,一般是枚举对称轴然后不断扩展,时间复杂度$O(n^2)$。
暴力算法有两点缺点:

  1. 对称轴可能是一个字母也可能是两个字母之间,需要两次枚举。
  2. 扩展可能会出现多余的重复。

NOIP2015,2016简要题解

NOIP2015

day1

神奇的幻方

CF55D

传送门

简要题意

定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。
给定$l$,$r$,求$l$到$r$中有多少数是美丽的。
多组数据,$l,r\le 9\times 10^{18}$

约瑟夫问题的一些解法

约瑟夫问题:

有n个人,编号为$1..n$,从第1个人开始报数,报到m的人离开,求最后的幸存者。

算法1(Simple算法):

用队列模拟,可以算出每一次出队的人。

时间复杂度$O(nm)$

当n很小而m很大时,可以通过取膜将$O(nm)$优化为$O(n^2)$

UOJ164 V

传送门

题意:维护一个数列$a_1…a_n$,有以下5种操作:

  1. $a_l..a_r=a_l..a_r +x$
  2. $a_l..a_r=max(a_l..a_r-x,0)$
  3. $a_l..a_r=x$
  4. 查询$a_x$
  5. 查询$a_x$的历史最大值
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×