翻译

5 个 X

Ehab 喜欢数论，但是他讨厌数字 x，给你一个数组 a，找到最长的子串，使它们的和不能被 x 整除，或者确定不存在这种子串。

一个字符串的子串，是这个字符串从头或者尾去除 0 到 n 个连续字符。

输入格式

第一行输入整数 t，表示测试用例组数。

每个测试用例输入两行，第一行输入两个整数 n 和 x，第二行输入 n 个数字，表示数组 a。

输出格式

每个测试用例，输出满足条件的最长子串的长度，或者输出 -1。

分析

如果字符串和不能被 x 整除，那么直接输出 n。

否则，判断左右两边最短的不能被 x 整除的数字距离最近边的长度。然后输出 n - 长度。

如果数字都能被 x 整除，则输出 -1。

代码(Python3)

image.png

# https://codeforces.com/problemset/problem/1364/A
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    arr = list(map(int, input().split(" ")))
    n, x = arr[0], arr[1]
    arr = list(map(int, input().split(" ")))

    sum = 0
    left = -1
    right = -1

    # 计算总和 与 左边最近非 x 倍数的个数
    for index, value in enumerate(arr):
        sum += value
        if left == -1 and value % x != 0:
            left = index
    
        if value % x != 0:
            right = index
    
    pos = -1
    if left >= 0:
        pos = left + 1

    # 计算右边和左边最近非 x 倍数的个数
    if right >= 0:
        pos2 = n - right
        if pos > 0:
            pos = min(pos, pos2)
    
    # 统计答案
    result = n
    if sum % x == 0:
        if pos > 0:
            result -= pos
        else:
            result = -1

    print(result)

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.30 长春