This post is written in Chinese. Please consider using Google Translate

可以算是一道数学题吧。如果知道皮克定理就好写多了。皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：S = a + b/2 - 1。 根据三角形面积公式求出S。如果知道了b，那么三角形内部格点数目a也就求出来了。 可以证明，一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。 即b=gcd(n,m)+1. gcd(n,m)为n与m的最大公约数。 代入皮克公式，即可求出a的值.

USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: fence9 LANG: C++

Compiling... Compile: OK

Executing... Test 1: TEST OK [0.011 secs, 2840 KB] Test 2: TEST OK [0.000 secs, 2844 KB] Test 3: TEST OK [0.011 secs, 2844 KB] Test 4: TEST OK [0.000 secs, 2844 KB] Test 5: TEST OK [0.011 secs, 2844 KB] Test 6: TEST OK [0.000 secs, 2840 KB] Test 7: TEST OK [0.011 secs, 2840 KB] Test 8: TEST OK [0.000 secs, 2840 KB] Test 9: TEST OK [0.000 secs, 2840 KB] Test 10: TEST OK [0.000 secs, 2840 KB] Test 11: TEST OK [0.022 secs, 2840 KB] Test 12: TEST OK [0.000 secs, 2840 KB]

汗，USACO居然有重名的题.

/*
ID: cmykrgb1
PROG: fence9
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("fence9.in");
ofstream fo("fence9.out");
long n,m,p,ans;

void init()
{
    fi >> n >> m >> p;
}

long gcd(long x,long y)
{
    int tmp;
    while (y>0)
    {
        tmp=y;
        y=x % y;
        x=tmp;
    }
    return x;
}

void compute()
{
    double S,b;
    long w1,w2;
    S=p*m/2.0;
    w1=gcd(n,m);
    w2=gcd(m,abs(p-n));
    b=p+w1+w2;
    ans=S-b/2.0+1;
}

void print()
{
    fo << ans << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    compute();
    print();
    return 0;
}