4.27 每日一题题解

Yet Another Counting Problem

题目链接：http://codeforces.com/contest/1342/problem/C

涉及知识点：

思维/数学

solution：

(找到所有的[L,R]区间的x，满足(x)%(a))%(b eq (x)%(b))%(a)
(看一下数据范围，L和R都是小于等于1e18，a和b都是小于等于200)
(再看一下公式：(x)%(a))%(b eq (x)%(b))%(a)
(假如a = 4，b = 6，那么a和b的最小公倍数等于12)
(a = 4,所以x)%(a = (x+4))%(a，b = 6，x)%(b = (x+6))%(b)
(不难得到x)%(a = (x+12))%(a，x)%(b = (x+12))%(b)
(那么模数会产生周期性的规律，周期就是a和b的最小公倍数)
(同理，第一个)%(号和第二个)%(号是同周期的，所以我们可以理解为：)
(如果(x)%(a))%(b eq (x)%(b))%(a，a和b最小公倍数=12，那么(x+12))%(a)%(b eq (x+12))%(b)%(a)
(这样我们只要算一个周期即可)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 505;
ll ans[maxn] , pre[40005];
ll cnt = 0 , gc;
ll solve(ll x){
    ll y = x/gc;
    int z = x%gc;
    ll sum = y*cnt + pre[z];
    return sum ;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll a,b,q,l,r;
        scanf("%lld %lld %lld",&a,&b,&q);
        gc = a*b/__gcd(a,b);
        cnt = 0;
        for(int i=1;i<=gc;i++){
            if(i%a%b != i%b%a){
                cnt++;
            }
            pre[i] = cnt;
        }
        for(int j=1;j<=q;j++){
            scanf("%lld %lld",&l,&r);
            ans[j] = solve(r) - solve(l-1);
        }
        for(int j=1;j<=q;j++){
            printf("%lld ",ans[j]);
        }
        printf("
");
    }
    return 0;
}