洛谷 P4132 [BJOI2012]算不出的等式

题意显而易见，不用描述

思路

思路题+数学函数

30pts

按题意暴力枚举，简单粗暴

100pts

代码极短，但是想好久也想不出来= =，果然是思路题

当(p eq q)时：

构造函数(f(x)=lfloorfrac{xq}{p} floor)

思考函数(g(x)=lfloor x floor)的几何意义：在坐标系中横坐标为(x)，纵坐标小于等于(x)的整数个数

那么(f(x))就表示：在坐标中横坐标为(x)，纵坐标小于等于(frac{xq}{p})的数的个数

那么(sumlimits_{k=1}^{frac{p-1}{2}}f(k))就表示所有(in[1,frac{p-1}{2}])的整数所形成的的函数图像中所有的整数点，如下图

答案即为右下角三角内的整数点个数

同理令(t(k)=lfloorfrac{kp}{q} floor)，则(sumlimits_{k=1}^{frac{q-1}{2}}t(k))就表示所有(in[1,frac{q-1}{2}])的整数所形成的的函数图像中所有的整数点

容易发现这两部分一起组成了一个矩形，所以我们只需要考虑矩形(A(0，0)，B(frac{p-1}{2},0),C(frac{p-1}{2},frac{q-1}{2}),D(0,frac{q-1}{2}),)

所以最后答案就是(frac{(p-1)}{2} imesfrac{(q-1)}{2})

当(p=q)时：

[sumlimits_{k=1}^frac{p-1}{2} lfloorfrac {kq}{p} floor+sumlimits_{k=1}^frac{q-1}{2} lfloorfrac {kp}{q} floor=2 imessumlimits_{k=1}^{frac{p -1}{2}}k=2 imesfrac{(frac{p-1}{2}+1) imes frac{p-1}{2}}{2}=frac{(p-1)(p+1)}{4} ]

代码

30pts

/*
Author:Loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int p, q, ans;

signed main() {
  p = read(), q = read();
  int up1 = (p - 1) / 2, up2 = (q - 1) / 2;
  for (int k = 1; k <= up1; k++) 
    ans += (int)k * q / p;
  for (int k = 1; k <= up2; k++) 
    ans += (int)k * p / q;
  cout << ans << '
';
  return 0;
}

100pts

/*
Author:Loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e6 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

int p, q, ans;

signed main() {
	p = read(), q = read();
	if (p == q) return cout << (p - 1) * (p + 1) / 4 << '
', 0;
	cout << (p - 1) * (q - 1) / 4 << '
';
	return 0;
}