做网站还是做淘宝,网站标签图标代码,河北项目网在建项目,wordpress分类高亮正题 题目大意 n∗mn*mn∗m的矩阵#xff0c;求对角线经过多少个格子(经过格子内部才算)。 解题思路 FromZYCdalaoFrom\ ZYCdalaoFrom ZYCdalao的思路:::对于若(n,m)1(n,m)1(n,m)1(互质)则会经过nm−1nm-1nm−1个格子#xff0c;所以我们可以将n∗mn*mn∗m拆分成gcd(n,m)gcd(…正题 题目大意
n∗mn*mn∗m的矩阵求对角线经过多少个格子(经过格子内部才算)。 解题思路
FromZYCdalaoFrom\ ZYCdalaoFrom ZYCdalao的思路:::对于若(n,m)1(n,m)1(n,m)1(互质)则会经过nm−1nm-1nm−1个格子所以我们可以将n∗mn*mn∗m拆分成gcd(n,m)gcd(n,m)gcd(n,m)个n/gcd(n,m)∗m/gcd(n,m)n/gcd(n,m)*m/gcd(n,m)n/gcd(n,m)∗m/gcd(n,m)的格子于是我们发现答案就是(n/gcd(n,m)m/gcd(n,m)−1)∗gcd(n,m)(n/gcd(n,m)m/gcd(n,m)-1)*gcd(n,m)(n/gcd(n,m)m/gcd(n,m)−1)∗gcd(n,m) 也就是nm−gcd(n,m)nm-gcd(n,m)nm−gcd(n,m)
FromFromFrom本菜鸡的思路:::理论上应该走nm−1nm-1nm−1个格子但是每个对角线跨过的节点都可以节省一个格子总共节省gcd(a,b)gcd(a,b)gcd(a,b)个。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int a,b;
int main()
{scanf(%d%d,a,b);printf(%d,ab-__gcd(a,b));
}
