老 K 的博客

传送门

先是计算f。

显然第一维排序。

然后第二维CDQ分治。

CDQ分治时用树状数组处理第三维。

求\(a^x\equiv b(\mod p)\)的最小整数解，其中p不一定为质数。

普通的BSGS只能解决a,p互质的问题，当a,p不互质怎么办呢？

传送门

已知 \(a,b,X_1,p,t\) ，

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

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

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\)

求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

day1

神奇的幻方

传送门 ### 简要题意 定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。 给定\(l\),\(r\)，求\(l\)到\(r\)中有多少数是美丽的。 多组数据，\(l,r\le 9\times 10^{18}\)