HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)

题意:

有这样一个有关最大公约数的函数:
函数 f(x, y):

给出三个正整数n,m,p,你需要计算:

$$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$

 

n <= 666,666,666, m <= 666, p <= 666,666,666。

 

思路:

打表找规律。

但是找规律也要按照基本法

观察到m比较小,对于固定的j,容易看出f(i,j)和f(i+j*k,k)是等价的。

比赛的时候没做出来,因为纠结取整的问题…

解决办法竟然是….通过循环节观察orz

转载一篇靠谱的题解:

一开始,我自己假设先不考虑c。那么就变成了ΣΣi/gcd*j/gcd=Σj/gcd*Σi/gcd,如此一来,由于m比较小,我就可以枚举j,然后对应求出j所有的因子作为gcd,gcd确定之后再根据容斥来统计i/gcd的和。具体统计方法和15年沈阳regional的frog那题类似,用n的因子来进行暴力的容斥。但是很显然这样子很难把c的影响带进来,而且这里的c还要向下取整,更加的麻烦。

于是打表找规律,首先很容易知道f(i,j)=f(i+kj,j)。根据这个,在不考虑向下取整的情况下,对于同一个j,我们就可以列出一个等差数列,其中首项是i*j/f(i,j),公差为j*j/f(i,j)。但是这里要考虑这个向下取整。我们设i为模9为7的数j为9,可以打出如下i*j/f(i,j)的表,括号内为相邻值的差:

可以发现,每c组i*j/f(i,j)是一个循环节,也就是说可以看作c个等差数列,然后对于每一个等差数列,它的首项我们可以暴力算出,而公差也很容易求出。利用等差数列求和公式可以很快速的计算出结果。复杂度的话,我们需要枚举j和在j剩余系下的i,然后还有c个等差数列,复杂度为O(m^2logN)在接受范围之内。具体见代码:

 

以及。。膜真的很浪费生命啊?

一开始取了5个%,TLE,4个%,50%概率AC,3个%就比较稳得过了…

一个%大概300ms orz

 

 

 

今日头条笔试题_或与加(打表,构造)

给定 x, k ,求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算,例如 3 | 5 = 7。

比如当 x=5,k=1时返回 2,因为5+1=6 不等于 5|1=5,而 5+2=7 等于 5 | 2 = 7。

 

输入描述:

每组测试用例仅包含一组数据,每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

 

输出描述:

输出一个数y。

 

输入例子:

 

输出例子:

一看就是数学题…?
打表观察…

 

发现如果x的二进制表示中,如果某位为1,那么对应的y的位置上一定为0.

如果某位为0,那么对应的y的位置上可以为0也可以为1…

就是说…x的二进制表示中,为1的的那些位置是能改变的.

影响当前第几大的就是那些为0的位置…

所以我们可以把k转化成二进制表示,按顺序填充到x中为0的那些位置(主要可以填充到x最大权值的1之后的0的位置),然后得到的数就是x+y的答案,最后再减去x即可

因为数组开小了..第一次只过了90%….

果然是个废k了呜呜呜,数组开小这种错误我也是服了…