HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)
题意：
有这样一个有关最大公约数的函数: 函数 f(x, y):
1{
2 c=0
3 当 y>0:
4 {
5 c +=1
6 t = x % y
7 x = y
8 y = t
9 }
10 返回 c * x * x
11}
给出三个正整数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，我们就可以列出一个等差数列，其中首项是ij/f(i,j)，公差为jj/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
/* ***********************************************
Author :111qqz
Created Time :2017年11月02日 星期四 09时38分56秒
File Name :5970.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6LL n,m,p;
7LL f(LL x,LL y,LL &c)
8{
9 LL t;
10 while (y>0)
11 {
12 c++;
13 t = x % y;
14 x = y;
15 y = t;
16 }
17 return c * x * x;
18}
19int main()
20{
21 #ifndef ONLINE_JUDGE
22 freopen("./in.txt","r",stdin);
23 #endif
24 int T;
25 cin>>T;
26 while (T--)
27 {
28 scanf("%lld%lld%lld",&n,&m,&p);
29 LL ans = 0 ;
30 for ( int j = 1 ; j <= m ; j++)
31 {
32 for ( int i = 1 ; i <= j && i <= n ; i++)
33 {
34 LL c=0,fun = f(i,j,c);
35 for ( int k = 0 ; k < c; k++)
36 {
37 if (i+k*j>n) break;
38 LL a1 = (i+k*j)*j/fun ;
39 LL d = c*j*j/fun;
40 LL num = (n-i-k*j)/(c*j) + 1;
41 ans = (ans + num * a1 % p + (num-1)*(num)/2%p*d )%p;
42 }
43 }
44 }
45 printf("%lld\n",ans);
46 }
47 #ifndef ONLINE_JUDGE
48 fclose(stdin);
49 #endif
50 return 0;
51}