oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

periodicity Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

periodicity.html

Problem Description

Gug's AI is bored, so it has gone on a mental adventure. As Gug has provided a huge amount of computing power to his AI, it has generated an infinitely long array A, consisting of only positive integers, in its mind. The array A has a special property: it is periodic with period N. What this means is that Ax = Ax+N, for x ≥ 0.

Gug's AI will choose a random non-negative integer from which to start. Let this integer be s. It will then write down this number on a piece of paper. Then, it will compute the next number in the sequence s + As, and write that down. It will keep repeating this same action. i.e. if the last number that was written down was s, the next number written down would be s + As.

Given a number X, Gug wants to know, how many possible numbers could the AI have started with such that it, at some point, writes X on its piece of paper.

Input

The first line of input will contain two integers, N and X.

The second line of input will contain N integers, A0 to AN-1.

Output

The output should contain one line with one integer, the number of possible starting numbers such that Gug's AI will write the number X on its paper at some point.

Limits

For all subtasks: 0 ≤ X ≤ 1018, 1 ≤ Ai ≤ 106.

Subtask 1 (41%): 1 ≤ N ≤ 300000, 0 ≤ X ≤ 106.

Subtask 2 (5%): N = 1.

Subtask 3 (26%): 1 ≤ N ≤ 2000.

Subtask 4 (28%): 1 ≤ N ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Input 1

1 4
2

Sample Output 1

3

Sample Input 2

3 10
1 4 2

Sample Output 2

6

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
141221s256MBMinimum
25211s256MBMinimum
326521s256MBMinimum
428821s256MBMinimum
5021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o periodicity -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.