首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。