GreenHatHGのBlog

牛客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)==0就代 ...

牛客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.com ...

牛客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?typ ...

牛客 -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 ...

模运算 模运算一些基本规则 加法： $(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（a，b ...

判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串 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 s) ...

牛客—Applese 走迷宫 模拟题，就是给出个m×n矩阵，从(0,0)开始，输出一种方案能够不重复得走完所有的点并且回到起点，没有的话输出-1。 掉了两个坑： 特殊情况：1行2列或2行1列，没有考虑这个也可以回到原点，以为只要是m==1||n==1就不能走了 没有考虑到别的走法，以至于以为m%2==0就不能走了 有一个还需要的优化的地方就是代码逻辑。 解析 主要是两种情况，当n%2==0时，可以按照下面这种走法输出方案 当n%2!=0&&m%2==0时，可以按照下面这种走法输出方案 其他情况都没有方案，输出-1 代码逻辑方面，有一部分都是一样的输出，所以可重复利用，如红色部分。所以可精简代码。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071/*提交时间：2019-01-29 19:41:29 语言：C++ 代码长度：1360 运行时间： 5 ...