Codeforces1243C Tile Painting

原题面：https://codeforces.com/contest/1243/problem/C

题目大意：给定数字n，有n个方块，第i个和第j个之间的距离(abs(i-j))如果是n的因子，那么第i块和第j块颜色相同，统计一下最后有多少种不同颜色的方块。

输入描述：输入一个正整数n。

输出描述：输出一共有多少种颜色不同的方块。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

分析：这个题猜了好几个结论才过了，我把它想的有点抽象，应该理解求最小循环节问题才对。这样就只用对n的所有因子求最小公因数，就是最小循环节。

代码：

def gcd(a, b):

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

n = input()

n = int(n)

i = 2

ans = n

while i * i <= n:

    if n % i == 0:

        ans = gcd(ans, i)

        ans = gcd(ans, n//i)

    i += 1

print(ans)

巴特西

Codeforces1243C Tile Painting

最新文章

热门文章