原文链接：https://blog.csdn.net/FOWng_lp/article/details/89288426

没搞明白的最大生成树 Nicoleta and the circle of kids codeforces/gym/101875/problem/A

A. Nicoleta and the circle of kids
time limit per test2.0 s
memory limit per test256 MB
inputstandard input
outputstandard output
Nicoleta is a happy kid, he goes every day to school and is always complaining about waking up early and having to complete his homework assignments. His favorite professor, Afonsox, is very funny and created a new challenge for him.

Even though Nicoleta is just a kid, Afonsox introduced him to the world of graph theory. Nicoleta is amazed, he is very obsessed with this graph that Afonsox decided to call K-round graph. A K-round graph with N vertices is a graph where every vertex u, numbered from 0 to N - 1, has an edge to vertices (u + 1)%N, …, (u + K)%N. Here a%b is the operator that gives the remainder of the integer division of a by b. Also, an edge between vertices u and (u + i)%N has value i.

Nicoleta likes this graph because if you draw it, it looks like a circle of kids, where each kid has K arms with different lengths with which they can reach the K next kids, like the picture below, which he drew in his notebook. Imagining this makes Nicoleta smile.

Figure: A 2-round graph with 4 vertices drawn by Nicoleta.
The challenge Afonsox has proposed to Nicoleta is for him to find the sum of all the values of the edges in the maximum spanning tree of a given K-round graph. A maximum spanning tree of a graph is composed of all of its vertices and a subset of edges such that there is one and only one path from one vertex to another and the sum of the values of the edges is maximal. Can you help Nicoleta finding the answer to Afonsox challenge?

Input
The input consists of a single line containing two integers N and K (1 ≤ K < N ≤ 109), indicating the number of vertices in the graph and the number of outgoing edges from every vertex.

Output
Output a single integer - the sum of the values of the edges in the maximum spanning tree of the K-round graph.

Examples
inputCopy
3 2
outputCopy
4
inputCopy
6 2
outputCopy
9

the problem’s link

http://codeforces.com/gym/101875/problem/A

the problem meaning

there are N kids round a circle , and they need hand in hand one by one . and they can hand in hand with the far from not over K distance . your task is to find longest distance they can hand in hand .put the distance

data range

N and K (1 ≤ K < N ≤ 1e9)

My idea

I have no idea , and find their’s , they write that if N is mutually qualitative with K（NK互质）the ans is (n - 1)*k
else ans is (N - GCD(N,K))K+(GCD(N,K)-1)(K-1)The greatest common divisor(最大公约数)

notice we can use GCD !!! __gcd(n,k) notice that there are double "_"

AC code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
long long n, k;
cin>>n>>k;
long long res = 0;
long long g = __gcd(n, k);
if(g != 1)//有公约数
    res = (n - g) * k + (g-1) * (k-1);
else//==1 互质
    res = (n-1) * k;
cout<<res<<endl;
return 0;
}