题目链接 SGU106 题目大意 已知$a,b,c,xl,xr$，求方程$ax+by+c=0$,$x\in[xl,xr],\ y\in[yl,yr]$的整数解个数.所有数不大于 $10^8$ 解题思路 将上式转化成 $ax+by=-c$。令 $c=-c$，即 $ax+by=c$。 将此时的$a,b,c$变成正数： 如果 $c<0$，则 $a,…

题目链接： 洛谷P1835 素数密度 题目大意： 给定区间$[L，R],(L≤R≤2147483647,R-L≤1000000)$，请计算区间中素数的个数。 #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 50; const int LEN = 1e6 …

51nod 1060 最复杂的数 51nod 1060 最复杂的数 题目大意： 把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。$(n\le 10^{18}, T\le 100)$ 例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。 即求 $n$ …

51nod 1061 最复杂的数V2 51nod 1061 最复杂的数V2 题目大意： 把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。 例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。 即求 $n$ 以内最大的反素数。 数据范围： $n\le …

P2480 [SDOI2010]古代猪文 题目大意： 给定 $G,n$，$1\le G,n\le 10^9$，求： $$ G^{\sum_{k|n}\binom{n}{k}}\bmod 999911659 $$ 分析： 由于 $P=999911659$ 是质数，所以当 $G\bmod P=0$ 时，答案为 $0$；否则： $$ ans=G^{\su…

2019牛客多校第五场C generator3 题目大意： 给你 $n,x_0,a,b,p$，$x_i=(a\cdot x_{i−1}+b)\bmod p$。给你 $q$ 组询问 $v$，问你各个 $x_i(i\in[0,n-1])$ 中最小的 $i$ 使得 $x_i=v$ 。$(1\leq n≤10^{18},\ 0\leq x_p,a,b &l…

2019南京网络赛 E. K SUM 题目大意： $$ f_n(k)=\sum_{l_1=1}^n \sum_{l_2=1}^n ... \sum_{l_k=1}^n \left(\gcd\left(l_1,l_2,...,l_k\right)\right)^2 $$ $$ 1 \le n \le 10^9,2 \le k \le {10}^{10…

题目链接：UVA11542 Square 题目大意： 有 $T$ 组数据，每组数据中有 $n$ 个数，分别为 $a_{1},a_{2},a_{3}...a_{n}$。从这 $n$ 个数中任选一个或多个数使得所取出来的数的乘积为完全平方数，问有多少种取法。 其中 $1 \leq T\leq 30,1 \leq N\leq 100,1 \leq a_{…

题目：2019牛客多校第一场 H.XOR 题目大意： 给你一个序列，问所有它的异或和为 $0$ 的子集大小之和。 $$ \left(\sum_{S \subseteq A, \oplus_{x \in S} x = 0} |S|\right) \bmod (10^9+7) $$ 解题思路： 先对 $n$ 个元素构造线性基 LB1，设其大小为 $r$…

题目：P3292 [SCOI2016]幸运数字 题目大意： 给一颗树 $(n\le 10^4)$，每个点有一个权值。有 $q$ 组询问 $(q\le 10^5)$，问两点之间树上路径点的最大异或和。 解题思路： 首先树剖，给点重新赋 $id$；用树剖算 lca 的过程中，对每条链维护一个线性基，每次将链的线性基和答案的线性基合并。由于经过了树剖重新…