zoj 3647 Gao the Grid

野性酷女 2021-09-19 12:28 241阅读 0赞

地大校赛出了这道原题，不会写，现在补一下。  
首先，我们很容易得到答案为 C ( ( n + 1 ) ∗ ( m + 1 ) , 3 ) − C ( n + 1 , 3 ) ∗ ( m + 1 ) − C ( m + 1 , 3 ) ∗ ( n + 1 ) − 斜 边 3 点 共 线 的 情 况 数 C((n+1)\*(m+1),3) - C(n+1,3)\*(m+1) - C(m+1,3) \* (n+1) - 斜边3点共线的情况数 C((n\+1)∗(m\+1),3)−C(n\+1,3)∗(m\+1)−C(m\+1,3)∗(n\+1)−斜边3点共线的情况数  
比赛时不会求斜边3点共线的情况  
一条边上经过的整点数(包括端点)为 b i = g c d ( a b s ( P 0. x − P t . x ) , a b s ( P 0. y − P t . y ) ) + 1 b\_i=gcd(abs(P0.x−Pt.x),abs(P0.y−Pt.y))+1 bi=gcd(abs(P0.x−Pt.x),abs(P0.y−Pt.y))\+1  
对于这一题，枚举点到(0,0)的情况，考虑斜边平移，答案就为  ∑ i = 2 n ∑ j = 2 m ( g c d ( i , j ) − 1 ) ∗ ( n − i + 1 ) ∗ ( m − j + 1 ) ∗ 2 \\sum\_\{i = 2\} ^ n\\sum\_\{j = 2\} ^ m(gcd(i,j)-1)\*(n-i+1)\*(m-j+1) \* 2 ∑i=2n∑j=2m(gcd(i,j)−1)∗(n−i\+1)∗(m−j\+1)∗2（乘2是考虑对角线相反的情况）

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    
    int T;
    ll n,m;
    
    ll gao(ll x)
    { 
    	return x * (x-1) * (x-2) / 6;
    }
    int main(int argc, char const *argv[])
    { 
    		ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    		while(cin >> n >> m)
    		{ 
    			ll ans = gao((n+1) * (m + 1) ) - gao(n+1)*(m+1) - gao(m+1) * (n+1);
    			rep(i,2,n+1)
    			{ 
    				rep(j,2,m+1)
    				{ 
    					ans -= (gcd(i,j)-1) * (n - i + 1) * (m - j + 1) * 2;
    				}
    			}
    			cout << ans << endl;
    		}
    	return 0;
    }