首页 > 代码库 > usaco-3.4-fence9-passed

usaco-3.4-fence9-passed

这个要知道一个公式;

可以算是一道数学题吧。如果知道皮克定理就行了。皮克定理说明了其面积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的最大公约数。

/*ID: qq104801LANG: C++TASK: fence9*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>using namespace std;#define nmax 27int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}void test(){        freopen("fence9.in","r",stdin);    freopen("fence9.out","w",stdout);      int n,m,p,b=0,s;    cin>>n>>m>>p;    s=(m*p)/2;    b+=gcd(n,m);    if(n!=p)b+=gcd(abs(n-p),m);    else b+=m;    b+=p;    cout<<s+1-(b/2)<<endl;}int main () {            test();            return 0;}

test data:

USACO TrainingGrader Results     26 users onlineARE/1 BGD/1 CHN/8 DNK/1 EGY/1 GEO/2 IND/2 IRN/1 ISR/2 MAC/1 MYS/1 TWN/1 USA/4USER: cn tom [qq104801]TASK: fence9LANG: C++Compiling...Compile: OKExecuting...   Test 1: TEST OK [0.003 secs, 3372 KB]   Test 2: TEST OK [0.005 secs, 3372 KB]   Test 3: TEST OK [0.005 secs, 3372 KB]   Test 4: TEST OK [0.008 secs, 3372 KB]   Test 5: TEST OK [0.008 secs, 3372 KB]   Test 6: TEST OK [0.008 secs, 3372 KB]   Test 7: TEST OK [0.008 secs, 3372 KB]   Test 8: TEST OK [0.008 secs, 3372 KB]   Test 9: TEST OK [0.005 secs, 3372 KB]   Test 10: TEST OK [0.008 secs, 3372 KB]   Test 11: TEST OK [0.005 secs, 3372 KB]   Test 12: TEST OK [0.005 secs, 3372 KB]All tests OK.YOUR PROGRAM (‘fence9‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----1 1 2------- test 2 ----2 2 4------- test 3 ----10 20 10------- test 4 ----0 100 100------- test 5 ----0 200 20000------- test 6 ----100 200 50------- test 7 ----10000 100 10------- test 8 ----0 20000 2------- test 9 ----200 30000 30000------- test 10 ----30000 30000 30001------- test 11 ----15000 100 30000------- test 12 ----0 31999 31999Keep up the good work!Thanks for your submission!

 

usaco-3.4-fence9-passed