C - Jumps on a Circle

SDUT 2022 Spring Team Contest(for 21) - 15 - Virtual Judge

There are p points on the circle numbered from 0 to (p - 1) in a way that from the point 0 you can move to the point 1, from the point 1 — to the point 2, and so on, and from the point (p - 1) you can move to the point 0.

A chip is initially placed at the point 0. It starts to jump around the circle, first moving 1 point forward, then 2 points forward, then 3 points forward and so on.

How many unique points (including the start one) will be visited by a chip after n moves?

Input

The input has two integers p and n (1 ≤ p ≤ 107, 0 ≤ n ≤ 1018) — the number of points on a circle and the number of moves.

Output

Output a single integer — the number of unique points visited by a chip.

Sample 1

3 10

2

Sample 2

5 3

3

Sample 3

8 1000000000000000000

8

题意：一个环从0到p-1，从0开始每次跳1,2,3，···，n-1，n步，问跳n步之后会有多少个位置访问过。

思路：弄一个vis数组，表示访问过的点，注意p为1e7，数组开大点（不然容易RE)

然后若n>2p,2p次后又一定回到点原点，然后2p+1,2p+2步的效果相当于1，2步（%p就知道了）

#include
#define int long long
using namespace std;
const int N=1e7+10;
int vis[N];
int n,p;
signed main()
{
    int now=0,sum=0;
    scanf("%lld %lld",&p,&n);
    vis[0]=1;//编号只能从0开始，如果从1开始，下面如果(now+i)被整除，now就等于0啦
    for(int i=1;i<=min(2*p-1,n);i++)
    {
        now=(now+i)%p;
        vis[now]=1;
    }
    for(int i=0;i