进制的应用
天梯赛练习L1-050 倒数第N个字符串题目123时间限制: 400 ms内存限制: 64 MB代码长度限制: 16 KB 题目描述 给定一个完全由小写英文字母组成的字符串等差递增序列,该序列中的每个字符串的长度固定为 L,从 L 个 a 开始,以 1 为步长递增。例如当 L 为 3 时,序列为{ aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz }。这个序列的倒数第27个字符串就是zyz。对于任意给定的 L,本题要求你给出对应序列倒数第 N 个字符串。 输入 输入在一行中给出两个正整数 $L(2 ≤ L ≤ 6)$和$N (N≤10^5)$。 输出 在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。 输入样例 13 7417 输出样例 1pat 解析L个字符就是L位的26进制数,告诉我们n是倒数的位置,那么我们求一下正着数的位置,然后将求得的10进制数字转化为26进制(每位26进制用小写的26个字符表示),这样求得的字符串就是外面需要的字符串。 如何求正数呢? 用总数减去倒数的就...
Rinne Loves Math
牛客70j-Rinne Loves Math 题目123时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld 题目描述 给了你形如$\sqrt{n}$的式子中的 n,让你输出化简后的结果 $a\sqrt{b}$ 中的 a,b,如果这样的式子在实数范围内没有意义,输出 -1。 输入描述 12第一行一个整数 T,表示数据组数。接下来 T 行,每行一个整数 x 表示根号下的数。 输出描述 1输出一共 T 行,每行两个数表示化简后的答案 a,b 示例1 输入 1234542025-200511 输出 12342 55 1-11 11 说明 20=4×525=5×5实数范围内$ \sqrt{n} $中 n 小于 0 没有意义。11 是个质数。 备注 $T≤100, 0<|x|≤10^7$ 题解比较水的模拟题,但是比赛时想错了,想得有点麻烦了,以为只除4和9就行了,emmm,不过还好最后做出来了。既然是化简,那么肯定是平方,所以逆序遍历$x\in[0,sqrt(n)]$,如果有n%(x*x)==...
区间或和
牛客332G-区间或和 题目123时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld 题目描述 求$a|(a+1)|(a+2)|…|(b-1)|b$。 其中|表示按位或 输出描述 1对于每组输入,输出一个数a|(a+1)|(a+2)|...|(b-1)|b。 示例1 输入 1234599 10968 7755 6634 431111234 1114321 输出 1234511179127471179647 备注 输入不超过10000行,$0≤a,b≤10^{18},a≤b$ 解析如果 a=b ,那么答案 =a ; 否则 a≠b , 考虑a和b的二进制表示从高到低第一个不同的位i, 必定b的第i位=1,a的第i位=0。 那么可以断定,对于答案的二进制表示, (1) 比第i位更高的那些位一定跟a相同。 (2) 第i位及比第i位更低的那些位一定为1。 (1)是显然的,(2)是由于把a中比第i位更低的那些位都置为1得到的数一定在区间[a,b]中 参考: https://ac.nowcoder....
出题
牛客323A-出题 题目123时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld 题目描述 小B准备出模拟赛。 她把题目按难度分为四等,分值分别为6,7,8,9。 已知小B共出了m道题,共n分。 求小B最少出了多少道6分题。 输入描述 1两个正整数n,m 输出描述 12一个数,表示答案。若无解,输出"jgzjgzjgz"。 示例1 输入 134 5 输出 11 示例2 输入 132 5 输出 13 示例3 输入 15 1 输出 1jgzjgzjgz 备注 $n,m\leq10^{12}$ 解析显然,有解的充要条件为 $6m≤n≤9m$ 。 若有解: 设有 $x(0≤x≤m)$ 道6分题,则剩下的$m-x$题共$n-6x$分, 则剩下的题有解的充要条件为$7(m−x)≤n−6x≤9(m−x)$ , 解得 $7m−n≤x≤(9m−n)/3$。 因此答案为$max(0,7m-n)$。 参考: https://ac.nowcoder.com/discuss/153349?...
Applese-涂颜色
牛客 -330E Applese 涂颜色 题目123时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld 题目描述 精通程序设计的 Applese 叕写了一个游戏。在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 $10^9+7$取模。 输入描述 1仅一行两个正整数 n, m,表示方阵的大小。 输出描述 1输出一个正整数,表示方案数对10^9+7取模。 示例1 输入 11 1 输出 12 示例2输入 12 2 输出 14 备注 $1\leq n,m\leq10^{100000}$ 题解一个比较显然的结论是,对于每一列,有$2^n$种涂色方法。我们可以发现,当确定了第一列之后,由于左右相邻不能同色,所以后面每一列的涂色方案也随之确定。因此答案就是 $2^n$ 首先n的数字范围非常大,10的10万次方,所以数据一定是用字符串读进去的,其次,因为 n 很大,循环n次肯定超时...
欧拉函数
欧拉函数公式,性质,模板 欧拉函数对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目。例如φ(8)=4,因为1,3,5,7均和8互质。 欧拉函数公式 euler(x) =x\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times......\times(1-\frac{1}{p_n})(其中p1, p2……pn为x的所有质因数,x是不为0的整数) 注意: φ(1) = 1(唯一和1互质的数(小于等于1)就是1本身)。 (注意:每种质因数只一个。比如 12 = 2\times2\times3 那么 φ(12) = 12\times (1-\frac{1}{2}) \times (1-\frac{1}{3})=4 ) 性质 当n为质数时,$φ(n)=n-1$。 当$n=p^k$时(p是素数),$φ(n)=φ(p^k )=p^k-p^{k-1}=(p-1)p^{k-1}$ 若n,m互质,$φ(nm)=φ(n)φ(m)=(n-1)(m-1)$ 若n是奇数,则$φ(2n)=φ(n)$ 特殊性质 当a与n互质时(n>2)有...
模运算
模运算 模运算一些基本规则 加法: $(a+b)\mod n=(a \mod n+b \mod n)\mod n$ 减法: $(a-b)\mod n=(a \mod n-b \mod n)\mod n$ 乘法: $(a∗b)\mod n=(a \mod n∗b \mod n)\mod n$ 幂: $a^b \mod n=(a \mod n)^b mod \ n$ 注意!除法不成立。 那么,如何计算$(a/b)\ mod\ n$? 我们可以通过将除b转换成乘b的逆元来解决,即$(a∗b^{-1} )\mod n$ 求$(a/b)\ mod\ m $逆元定义对于正整数$a$和$m$,如果有$ax\equiv 1(\ mod\ m)$,那么把这个同余方程中的$x$最小正整数解叫做$a$模$m$的逆元。 逆元的存在性质:当$a$与$m$互素的时候,逆元才存在解,如果不互素则无解(这里说的都是整数解) 求法逆元一般用扩展欧几里得算法来求得,如果$m$为素数,那么还可以根据费马小定理得到逆元为$a^{m-2}\ mod\ m$。(都要求$a$和$m$互质) 费马小定理求解(m为素数...
素数筛快速幂
素数筛快速幂 素数筛埃氏筛法—-求解n以内的素数个数1234567891011121314151617181920int prime[MAXN]; //第i个素数的值bool is_prime[MAXN]; //is_prime[i]为true时表示i是素数//返回n以内素数的个数int solve(int n){ int p = 0; //代表素数个数 for(int i = 2; i <= n; i++) is_prime[i] = true; for(int i = 2; i <= n; i++) { if(is_prime[i]) { prime[p++] = i; //每有一个素数,p就++,然后prime存的就是素数的值,然后进行筛选 for(int j = i * i; j <= n; j += i) is_prime[j] = false; } &...
欧几里得
gcd, lcm, exgcd 欧几里得—最大公约数gcd(a, b) = gcd(b, a mod b)123456int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % )b;} 一波应用:线段上格点个数—-挑战编程—-欧几里得 algorithm库的std::_gcd函数123456789101112#include <iostream>#include <algorithm>using namespace std;int main(){ int a = 8; int b = 12; cout <<__gcd(a, b); //两个'_' return 0;}//out:4 //g++-4.8 最小公倍数(LCM)和最大公约数(GCD)lcm(a, b) = (a*b)/gcd(a,b) 扩展欧几里得基本算法:对于不完全为 0 的非负整数 a,b,gcd(...
牛客--applese的回文串
判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串 Applese 的回文串 解析 TAG:思维,想法 可以认为插入和删除是等价的操作。想到这一点,这题就会好做很多。如果这个串本身就是回文串,答案一定是Yes。否则我们只需要考虑串中对称的位置不相等的两个字符,分别尝试把它们删掉后判断一下是不是回文的就行了。 参考自:https://ac.nowcoder.com/discuss/153012?type=101 123456789101112131415161718192021222324252627282930313233343536373839404142434445/*提交时间:2019-01-30 12:03:32 语言:C++ 代码长度:695 运行时间: 4 ms 占用内存:996K 运行状态:答案正确*/#include <iostream>#include <string>using namespace std;//判断对称位置的字符是否相等,相等返回-1,不是返回不相等的位置int check(string...