[HDU-6847] Decision (2020多校7T4) (类欧几里得问题)

枚举$|v_1-v_2|$后，可以递推，用含首项($v_1+v_2$)的一次函数表示函数值为$a(v_1+v_2)+b$，则问题等价于求

$\begin{aligned} \sum_{i=0}^n [2|(ai+b)\mod m] \end{aligned}$ ，其中 $n$ 对于每个 $v_1-v_2$ 是不同的 这个问题，可以转化为一个简单的类欧几里得问题 $(ai+b)\mod m \mod 2= ((ai+b)-(m\mod 2)\cdot \lfloor \frac{ai+b} {m}\rfloor )\mod 2$ 这个式子即把每次被$m$取模减少的$m$算进贡献 可以看到操作非常简单，可以直接套上万能欧几里得的板子 当然，也可以对于$m$的各种情况讨论，转化为求$\lfloor \frac{ai+b} {m}\rfloor$，其主要思想还有应用 $x\mod 2=x-2\cdot \lfloor \frac{x} {2}\rfloor$ 的转化 我比赛时去抄了自己的类欧几里得模板 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1e6+10;

int t,a,c,m;
int fx[N],fy[N];

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

ll D2(ll n){
    return n*(n+1)/2;
}
ll F(ll a,ll b,ll c,ll n){
    if(n<0) return 0;
    if(a==0) return (b/c)*(n+1);
    if(a>=c || b>=c) {
        ll ans=F(a%c,b%c,c,n)+D2(n)*(a/c)+(n+1)*(b/c);
        return ans;
    }
    ll t=(a*n+b)/c;
    ll ans=t*n-F(c,-b+c-1,a,t-1);
    return ans;
}

ll CalcMod(int a,int b,int m,int n){
    return F(a,b,m,n)-F(a,b,m*2,n)*2;
}

ll Calc(int a,int b,int n){
    // for i= [l,r] (ax+b) %m %2
    if(~m&1){
        // (ax+b)%2;
        a%=2,b%=2;
        if(a==0) return b*(n+1);
        return (n+1+b)/2;
    } else {
        // (ax+b) %m %2 = ((ax+b)/m + ax+b)%2
        int c=a%2,d=b%2;
        if(c==0) {
            // =((ax+b)/m+b)%2;
            if(d==0) return CalcMod(a,b,m,n);
            else return (n+1)-CalcMod(a,b,m,n);
        } else {
            // (ax+b) %m %2 = ((ax+b)/m + (x&1)+d)%2
            ll ans=0;

            // i%2 == 0
            ll t=CalcMod(a*2,b,m,n/2);
            if(d) t=n/2+1-t;
            ans+=t;

            b+=a;
            // i%2 == 1
            n--;
            if(n<0) return ans;
            t=CalcMod(a*2,b,m,n/2);
            if(!d) t=n/2+1-t;
            ans+=t;
            return ans;
        }
    }
}

int main(){
    rep(kase,1,rd()) {
        t=rd(),a=rd(),c=rd(),m=rd();
        fx[0]=1,fy[0]=0;
        rep(i,1,t) fx[i]=1ll*fx[i-1]*a%m,fy[i]=(1ll*fy[i-1]*a+c)%m;
        ll ans=0;
        rep(i,0,t) {
            if(i==0) {
                ans+=Calc(fx[i]*2%m,fy[i],t);
            } else {
                // a<b, b - a = i
                // a=[0,m-i]
                // b=[i,m]
                ll tmp=(1ll*i*fx[i]+fy[i])%m;
                ans+=Calc(fx[i]*2%m,tmp,t-i)*2;
            }
        }
        ll tmp=1ll*(t+1)*(t+1);
        ans=tmp-ans;
        ll g=gcd(tmp,ans);
        printf("%lld/%lld\n",ans/g,tmp/g);
    }
}