【容斥原理、gcd】初步

有很多很多東西

目前隻搞了幾道較基礎的，還有資料範圍增大幾萬倍的加強版

一. noi-2010-energy

http://61.187.179.132/JudgeOnline/problem.php?id=2005

<1.80分算法O(nmlogn)

   觀察圖後顯然可得，過(0,0)~(n,m)兩點的直線上的整點數為2*gcd(n,m)-1(要知道如何證明)

<2.100分算法O(nlogn)

   f[i]記錄gcd值為i的點的個數，初值為(m / i)*(n / i), 即為有因子i的點的個數，是以再利用容斥原理算出f[i]的正确值

感覺此題複雜度分析有誤的樣子，但是反正是很久之前寫的不管了