?C-小紅的數組查詢（二）_牛客周賽 Round 95

?思路：不難看出a數組是有循環的

d=3,p=4時，a數組：1、0、3、2、1、0、3、2.......? 最小循環節為4，即最多4種不同的數

d=4,p=6時，a數組：1、5、3、1、5、3.......最小循環節為3

d=4,p=10時，a數組：1、5、9、3、7、1、5、9、3、7.......最小循環節為5

可以得出，最小循環節T=p / gcd(d,p)

?

ans=min(詢問的區間長度，最小循環節)

ans=min(r-l+1,T)

特殊情況：p=1時，a數組：1、0、0、0........(任何數對1取模均為0)

l=1,r>1時，ans=2

其余，ans=1

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {ll d,p,q;cin>>d>>p>>q;// 將d對p取模，因為后續的計算是基于模p的d = d % p;// 計算d和p的最大公約數gll g = __gcd(d, p);// 計算T，即周期長度，T = p / gll T = p / g;// 處理q次詢問while (q--) {ll l, r;cin >> l >> r;// 特殊情況：如果p == 1，那么所有元素都是0（因為任何數mod 1都是0）if (p == 1) {// 如果區間長度大于1，那么只有0和1兩種元素（因為a1=1，其他都是0）ll ans = 1;if (l == 1 && r > 1) {ans++;}cout << ans << endl;continue;}// 計算區間內的元素種類數// 如果區間長度小于T，那么元素種類數就是區間長度，// 否則，元素種類數就是Tcout << min(r - l + 1, T) << endl;}
}