ARC084B Small Multiple
求k的倍数中数位和的最小值。
求k的倍数中数位和的最小值。
设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)(from 51nod)
k有原根当且仅当$k=2,4,p^a,2p^a$
其中p是奇素数,a是正整数
暴力枚举判断是不是满足条件。
(首先保证$\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)$。
暴力算法有两点缺点:
扩展可能会出现多余的重复。
定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。
给定$l$,$r$,求$l$到$r$中有多少数是美丽的。
多组数据,$l,r\le 9\times 10^{18}$