BearChild's Blog

Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k Output 共n行，每行一个整数表示满足要求的数对(x,y)的个数。 Sample Input 2 　2 5 1 5 1 　1 5 1 5 2 Sample Output 14 　3 HINT 100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000 Solution 显然可以考虑容斥，分为四块来做，剩下的就是： Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...

YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Description 求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对k。 Input 第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M。 Output T行，每行一个整数表示第 i 组数据的结果 Sample Input 2 　10 10 　100 100 Sample Output 30 　2791 HINT T = 10000 　N, M <= 10000000 Solution Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<bits/stdc++.h>using namespace std;typedef long long s64;const in ...

Zap Time Limit: 10 Sec Memory Limit: 162 MB Description 对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。 Input 第一行包含一个正整数n，表示一共有n组询问。接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。 Output 输出一个正整数，表示满足条件的整数对数。 Sample Input 2 　4 5 2 　6 4 3 Sample Output 3 　2 HINT 1<=n<= 50000, 1<=d<=a,b<=50000 Solution 我们运用莫比乌斯反演，然后推一下式子得到： 我们依旧对于下界分块求解即可。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc+ ...

jzptab Time Limit: 10 Sec Memory Limit: 512 MB Description 求 $ \sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i,j) $ Input 第一行一个 T 表示数据组数 接下来T行 每行两个正整数 表示N、M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 　4 5 Sample Output 122 HINT T <= 10000 　N, M<=10000000 Solution 我们先根据 [Crash的数字表格] 运用莫比乌斯反演推到一个式子，然后优化求解： Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<bits/stdc++.h>using namespace std;typedef ...

光 Time Limit: 10 Sec Memory Limit: 128 MB Description 天猫有一个长方形盒子，长宽分别为A，B。 　　这个长方形盒子的内壁全部是镜面。 　　天猫在这个盒子的左下方放了一个激光灯。 　　这个灯可以照向盒子内的任意角度。 　　现在天猫想要打开这个激光灯，但是他想让光线按照如下规则照射： 　　　　1.这束光必须恰好打到盒子边缘反射D次，并且不能碰到任意一个角落（除了出发点以及结束点）。 　　　　2.这束光必须到达盒子右上角，并且结束反射。 　　天猫想要知道，所有合法的光线路线的长度平方和是多少。 　　作为一个资深OIer，你应该知道输出要对10^9+7取模。 Input 一行三个数，表示A、B、D。 Output 一个数，表示路径平方和。 Sample Input 3 3 2 Sample Output 180 HINT D<=10^9, A,B<=10^6 Solution 首先，我们注意到若一束光在一个平面反射，相当于镜面一侧的物体对称到镜面另一侧，而光线穿过镜面照到物体成的虚像上。 　　所以，我们可以认为：有一个D∗D的网 ...

完全平方数 Time Limit: 10 Sec Memory Limit: 128 MB Description 小X自幼就很喜欢数。 　　但奇怪的是，他十分讨厌完全平方数。 　　他觉得这些数看起来很令人难受。 　　由此，他也讨厌所有是完全平方数的正整数倍的数。 　　然而这丝毫不影响他对其他数的热爱。 　　这天是小X的生日，小 W 想送一个数给他作为生日礼物。 　　当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。 　　小X很开心地收下了。 　　然而现在小 W 却记不起送给小X的是哪个数了。 　　你能帮他一下吗？ Input 包含多组测试数据。文件第一行有一个整数 T，表示测试数据的组数。 　第 2 至第 T+1 行每行有一个整数 Ki，描述一组数据，含义如题目中所描述。 Output 含 T 行，分别对每组数据作出回答。第 i 行输出相应的 　第 Ki 个不是完全平方数的正整数倍的数。 Sample Input 4 　1 　13 　100 　1234567 Sample Output 1 　19 　163 　2030745 HINT 对于 1 ...

数字表格 Time Limit: 50 Sec Memory Limit: 128 MB Description Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么 f[0]=0 f[1]=1 f[n]=f[n-1]+f[n-2],n>=2 Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,j的最大公约数。Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。 Input 第一个一个数T，表示数据组数。 接下来T行，每行两个数n,m Output 输出T行，第i行的数是第i组数据的结果 Sample Input 3 　2 3 　4 5 　6 7 Sample Output 1 　6 　960 HINT T<=1000,1<=n,m<=10^6 Solution 运用莫比乌斯反演，得到式子： 这样我们对于内外分块即可，复杂度为O(n^(0.75)*T)。 Code 1234567891011121314151617181920 ...

序列 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定长度为n的序列：a1,a2,…,an，记为a[1:n]。 　　类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。 　　若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。 　　现在有q个询问，每个询问给定两个数l和r，1≤l≤r≤n，求a[l:r]的不同子序列的最小值之和。 例如，给定序列5,2,4,1,3，询问给定的两个数为1和3， 　　那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]， 　　这6个子序列的最小值之和为5+2+4+2+2+2=17。 Input 输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。 　　接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。 Output 对于每次询问，输出一行，代表询问的答案。 Sample Input 5 5 　5 2 4 1 3 ...

Gty的二逼妹子序列 Time Limit: 80 Sec Memory Limit: 28 MB Description Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。 对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。 为了方便，我们规定妹子们的美丽度全都在[1,n]中。 给定一个长度为n的正整数序列s(1<=si<=n)，对于m次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。 Input 第一行包括两个整数n,m,表示数列s中的元素数和询问数。 第二行包括n个整数s1…sn(1<=si<=n)。 接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。 保证涉及的所有数在C++的int内。 保证输入合法。 Output 对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。 Sample Input 10 10 　4 4 5 1 4 1 5 1 2 1 　5 ...

mex Time Limit: 20 Sec Memory Limit: 128 MB Description 有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。 Input 第一行n,m。 　第二行为n个数。 　从第三行开始，每行一个询问l,r。 Output 一行一个数，表示每个询问的答案。 Sample Input 5 5 　2 1 0 2 1 　3 3 　2 3 　2 4 　1 2 　3 5 Sample Output 1 　2 　3 　0 　3 HINT 1<=n,m<=200000, 0<=ai<=1e9 Solution 首先，权值>n的显然是没有用的，最多排满1~n。然后我们直接使用莫队，对权值分块，查询的时候看一下这个块里面权值数是否满了，即可做到O(sqrt(n))的查询。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...