You are given two integers a and b, and q queries. The i-th query consists of two numbers li and ri, and the answer to it is the number of integers x such that li≤x≤ri, and ((xmoda)modb)≠((xmodb)moda). Calculate the answer for each query.

Recall that ymodz is the remainder of the division of y by z. For example, 5mod3=2, 7mod8=7, 9mod4=1, 9mod9=0.

Input
The first line contains one integer t (1≤t≤100) — the number of test cases. Then the test cases follow.

The first line of each test case contains three integers a, b and q (1≤a,b≤200; 1≤q≤500).

Then q lines follow, each containing two integers li and ri (1≤li≤ri≤1018) for the corresponding query.

Output
For each test case, print q integers — the answers to the queries of this test case in the order they appear.

Example
Input
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200
Output
0 0 0 2 4
0 91
思路：數學題，沒有什么思路就暴力打表找規律，我們可以發現以a*b為一個周期，這個周期內的特殊數的個數是確定的。那么我們就把[1,a *b]內的特殊數暴力找出來。dp[i]代表的是前i個數中有多少個特殊數。
對于輸入的l和r，我們只需要看他們中分別有多少個a * b以及對a * b取余是多少，然后加起來就可以了。分別對l和r計算出這個數，然后再用fcs?-fcs(l-1)前綴和思想。具體看代碼
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=4e4+100; int dp[maxx]; int a,b,q; int n;inline ll fcs(ll cnt) {return (ll)dp[n-1]*(ll)(cnt/n)+(ll)dp[cnt%n]; } int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&a,&b,&q);dp[0]=0;n=a*b;for(int i=1;i<=n;i++){if(i%a%b==i%b%a) dp[i]=dp[i-1];else dp[i]=dp[i-1]+1;}ll l,r;while(q--){scanf("%lld%lld",&l,&r);printf("%lld\n",fcs(r)-fcs(l-1));}}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Yet Another Counting Problem CodeForces - 1342C(规律+前缀和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。