题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2588 题目大意：给定整数N和M，有多少整数X满足1 <= X <= N且 gcd（X，N）> = M 第一行输入是整数T（T <= 100），表示测试用例的数量。以下T行每行包含两个数字N和M（2 <= N <= 1000000000,1 <= M <= N），表示测试用例 思路： 但是 n 的范围太大O(n)复杂度会超时 优化： 因为枚举 s>=m&&n%s==0， 如果s是n的因数则（n/s）也是n的因数，所...

题目链接：https://www.nowcoder.com/acm/contest/158/A T的取值[1, 20], n的取值[1,10^9] 思路：对于小于n每个数进行遍历查找因数暴力O(n^2)肯定超时 1~n约数的个数的和实际就是看1~n在这些数中出现过多少次，例如1是1~n每个数的因数，所以对1这个因数来说，出现了n / 1次，以此类推; 发现答案n / 1 + n / 2 + n / 3 + …… + n / n复杂度为O(n)，因为分母x大等于n/2时，n/x=1恒成立 理念上时间可能卡过去，提交T了 思考怎么继续进行优化 既然（n/x）=1有一个区间，那么=...

题目链接：http://47.93.249.116/problem.php?id=2141 题意是给你给一个数字串，问该数字串有多少个连续子串能整除3 因为能被3整除的数字串的和一定是3的倍数，一开始的思路是记录前缀和，再对每一个前缀和遍历之后的前缀和用后面的前缀和减去前面的前缀和如果差值为3的倍数则ans++ 但是时间复杂度为O(n^2)，而n<=1e6，肯定会T，这道题的正确思路是 思考：这个规律要记住，如果问数字串有多少个连续子串是k的倍数，该方法直接套用时间复杂度O(n) #include <iostream> #include <cs...

题目链接：http://codeforces.com/problemset/problem/1016/B 题意是给你给两个字符串s，t，之后给出s的q个区间，对每个区间[l,r]询问s的这个区间中存在多少个子串与t相同 一开始的思路是每给出一个区间[L,R]。便在s相应的区间用KMP进行查找t出现的次数,但是大佬们说自己暴力过了这题。而我的暴力一直TLE。后来在排行榜上找了份大神的代码,原来他们的暴力是:预处理是用一个数组sum记录字符串中t出现的次数。sum[i]记录s串中前i个字符中t串(头部在i)出现的总次数。查找时直接利用端点的前缀和相减 思考：前缀和在很多题中的确可以节约重...