luogu P4132 [BJOI2012]算不出的等式

传送门

以前的题

当时集训的时候老师连着笑话一起讲的

这题自己先找规律打表就猜是(p-1)*(q-1)/4

没有∑套∑ 先把式子分成两个(其实是一样的)

然后考虑这个式子求和前的每一项 

对于每一个k求的都是y=q/p*x下的整点数

然后另一边就是互补的一侧

(该式两部分分别是一个([p/2],[q/2])方格图主对角线分成的两部分的整点数.)[]表示下取整

图大概长这样

由于p,q是质数 所以只有相等的时候会有p个点会少算(边界)

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(a,b) memset(a,b,sizeof a)
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define inf 1000000007
using namespace std;
typedef long long ll;
typedef double D;
#define eps 1e-8
ll read() {
    ll as = 0,fu = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') fu = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        as = as * 10 + c - '0';
        c = getchar();
    }
    return as * fu;
}
//head
ll p,q,ans;
int main() {
    p = read(),q = read();
    ans = (p>>1)*(q>>1);
    if(p == q) ans += p>>1;
    printf("%lld
",ans);
    return 0;
}