首页 > 代码库 > HDU 5970 最大公约数

HDU 5970 最大公约数

2024-08-19 22:22:03   225人阅读

中文题

题意：

技术分享

 

思路：

1、观察可得 模m的同余系和m的gcd都相同（这题多了一个c也是相同的）

2、由于取证所以不能用简单的用O(m^2)的做法，涉及到多1少1的

3、打表观察，例如i为模9为7的数 j为9

则i*j/f(i,j) 有这样的规律：

技术分享

括号内为相邻值的差，而这个差是有循环节的，也就意味着，这可以看作4个等差数列。

又发现f(i,j)的c为4。

然后就大胆猜测c就是循环节。又试了几个数，果然是这样。

//不过很巧的是，循环节有一点小规律，但是没有仔细想，说不定可以有O(m^2)的做法

然后gcd的计算次数是log级别的，所以总的复杂度就是O(T*m^2*log(m))

 

//不过我的程序跑得不是很快。几乎是卡时间过的

具体细节看代码：

 1 LL f(int x, int y, int& g, int& c)
 2 {
 3     c = 0;
 4     int t;
 5     while (y)
 6     {
 7         c++;
 8         t = x % y;
 9         x = y;
10         y = t;
11     }
12     g = x;
13     return x * x * c;
14 }
15 
16 int n, m, p;
17 void init()
18 {
19     get_int(n);
20     get_int(m);
21     get_int(p);
22 }
23 
24 void solve()
25 {
26     int ans = 0, g, c;
27     for (int j = 1; j <= m; j++)
28     {
29         for (int i = 1; i <= j && i <= n; i++)
30         {
31             LL ff = f(i, j, g, c);
32             for (int k = 0; k < c; k++)
33             {
34                 if (i + k * j > n) break;
35                 LL a0 = (i + k * j) * j / ff;
36                 LL d = c * j * j / ff;
37                 LL num = (n - (i + k * j)) / (c * j) + 1;
38                 ans = ((ans + a0 * num) % p + num * (num - 1) / 2 % p * d % p) % p;
39             }
40         }
41     }
42     printf("%d\n", ans);
43 }
44 
45 int main()
46 {
47     int T;
48     get_int(T);
49     while (T--)
50     {
51         init();
52         solve();
53     }
54     return 0;
55 }

 

HDU 5970 最大公约数


联系
我们