网站推广 软件,广州网站建设哪个公司做得好些,广东网络推广运营,10个优秀的网页设计欣赏知识点#xff1a;(a, b)与(c, d)两点连线上点的个数为:gcd(x, y) 1(包括端点)
#xff08;设横坐标差的绝对值为x#xff0c; 纵坐标差的绝对值为y #xff09; 思路#xff1a;先算出选三个点的所有情况#xff0c;再减去三点共线的情况
共线的斜率为0时特判
当共线…
知识点(a, b)与(c, d)两点连线上点的个数为:gcd(x, y) 1(包括端点)
设横坐标差的绝对值为x 纵坐标差的绝对值为y 思路先算出选三个点的所有情况再减去三点共线的情况
共线的斜率为0时特判
当共线的斜率大于0时枚举共线的长和宽设为a、b则这条线左下角的选法有(n1-a)*(m1-b)种
对于每一种选法左下角看作第一个点右上角看作第二个点两点中间的点数就是选法个数即gcd(a, b) - 1。
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;
typedef long double ld;ll C(int a)
{if(a 3)return 0;ll res (ll)a * (a - 1) * (a - 2) / 6;return res;
}int main()
{IOSint n, m;cin n m;n , m ;ll ans C(n * m) - m * C(n) - n * C(m);n --, m --;for(int i 1; i n; i ){for(int j 1; j m; j ){ll res (n 1 - i) * (m 1 - j) * (__gcd(i, j) - 1);ans - res * 2;}}cout ans;return 0;
} 1310. 数三角形 - AcWing题库
