Modindrome
Source: codechef
Difficulty: 2278

Modindrome
For an array$B$of length$M$, define a function$f(B)$as follows:
Pick a positive integer$X$Consider the array$C$of length$M$, where$C_i = B_i\mod X$$X$is called
good
if$C$is a palindrome$f(B) =$the number of
good
positive integers$X$for the array$B$If there are infinitely many such$X$, then$f(B) = -1$Given integers$N$and$M$. Find the sum of$f(A)$over all arrays$A$of length$N$satisfying$1 \leq A_i \leq M$for all$i$. As the answer may be large, output the answer modulo$998244353$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of a single line of input.
The one and only line of each test case contains two space-separated integers$N$and$M$.
Output Format
For each test case, output on a new line the sum of$f(A)$over all arrays$A$of length$N$satisfying$1 \leq A_i \leq M$for all$i$, modulo$998244353$.
Constraints$1 \leq T \leq 10^4$$2 \leq N \leq 2*10^5$$2 \leq M \leq 2*10^5$The sum of$N$over all test cases won't exceed$2*10^5$.
The sum of$M$over all test cases won't exceed$2*10^5$.
Sample 1:
Explanation:
Test Case 1
:$A = [1,1]$: Any value of$X$is valid. Thus,$f(A) = -1$.$A = [1,2]$: Only$X = 1$is good. Thus,$f(A) = 1$.$A = [1,3]$: Only$X = 1$and$X = 2$are good. Thus,$f(A) = 2$.$A = [2,1]$: Only$X = 1$is good. Thus,$f(A) = 1$.$A = [2,2]$: Any value of$X$is valid. Thus,$f(A) = -1$.$A = [2,3]$: Only$X = 1$is good. Thus,$f(A) = 1$.$A = [3,1]$: Only$X = 1$and$X = 2$are good. Thus,$f(A) = 2$.$A = [3,2]$: Only$X = 1$is good. Thus,$f(A) = 1$.$A = [3,3]$: Any value of$X$is valid. Thus,$f(A) = -1$.
Thus, the sum of$f(A)$over all possible arrays$A = -1+1+2+1-1+1+2+1-1 = 5$.

Sample Input:
5
2 3
3 2
2 6
4 5
69 420

Sample Output:
5
0
48
799
465199511

C++ solution:
#include <bits/stdc++.h>
using namespace std;

const long long LIMIT = 1e7 + 10;
const long long MOD = 998244353;

long long powerMod(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

long long countValidPairs(long long m, long long x) {
    int multipleCount = (m - 1) / x + 1;
    int remainder = m - (m - 1) / x * x;
    int sum = ((remainder * multipleCount) % MOD * multipleCount) % MOD + 
              ((x - remainder) * ((multipleCount - 1) % MOD) * (multipleCount - 1) % MOD);
    return sum % MOD;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, m;
        cin >> n >> m;

        long long palindromeArrays = (n & 1) ? powerMod(m, (n + 1) / 2) : powerMod(m, n / 2);
        long long totalCount = 0;

        for (int x = 1; x <= m; x++) {
            long long pairCount = countValidPairs(m, x);

            if (n & 1) 
                totalCount = (totalCount + (powerMod(pairCount, n / 2) * m) % MOD) % MOD;
            else 
                totalCount = (totalCount + powerMod(pairCount, n / 2)) % MOD;

            totalCount = (totalCount - palindromeArrays + MOD) % MOD;
        }

        totalCount = (totalCount - palindromeArrays + MOD) % MOD;
        cout << totalCount << "\n";
    }

    return 0;
}

Go solution:
package main

import (
    "fmt"
)
const H = 998244353
func B(C, N int64) int64 {
    O := int64(1)
    C %= H
    for N > 0 {
        if N&1 == 1 {
            O = O * C % H
        }
        C = C * C % H
        N >>= 1
    }
    return O
}
func main() {
    var Li int
    fmt.Scan(&Li)
    for Li > 0 {
        Li--
        var Be, F int64
        fmt.Scan(&Be, &F)
        Ne := Be / 2
        Na := Be % 2
        Mg := int64(1)
        if Na != 0 {
            Mg = B(F, 1)
        }
        if Na != 0 {
            Mg = F % H
        }
        Al := int64(0)
        for Si := int64(1); Si <= F; Si++ {
            P := F / Si
            S := F % Si
            Cl := (S * ((P+1)*(P+1)%H)) % H
            Ar := ((Si - S) * (P * P % H)) % H
            K := (Cl + Ar) % H
            Ca := int64(1)
            if Ne != 0 {
                Ca = B(K, Ne)
            }
            Sc := Ca * Mg % H
            Al = (Al + Sc) % H
        }

        Ti := int64(1)
        if Ne != 0 {
            Ti = B(F, Ne)
        }
        Cr := Ti
        if Na != 0 {
            Cr = Cr * B(F, 1) % H
        } else {
            Cr = Cr * 1 % H
        }
        Mn := (1 + F) % H
        Cr = Cr * Mn % H
        Al = (Al - Cr) % H
        if Al < 0 {
            Al += H
        }
        fmt.Println(Al)
    }
}

Java solution:
import java.util.Scanner;

class Main {

    static final int MOD = 998244353;

    // Fast exponentiation: computes x^y % MOD
    static long powerMod(long x, long y) {
        long res = 1;
        x %= MOD;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            y >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            long N = sc.nextLong();
            long M = sc.nextLong();
            long K = N / 2;
            long M_mod = N % 2;
            long pow_m_mod = (M_mod == 1) ? powerMod(M, 1) : 1;

            // Precompute powers of M
            // Now, compute sum_f
            long sum_f = 0;
            for (long d = 1; d <= M; d++) {
                long a = M / d;
                long b = M % d;
                long term1 = (b * ((a + 1) * (a + 1) % MOD)) % MOD;
                long term2 = ((d - b) * (a * a % MOD)) % MOD;
                long sum_c_r_sq = (term1 + term2) % MOD;
                long pow_sum = (K == 0) ? 1 : powerMod(sum_c_r_sq, K);
                long contrib = pow_sum * pow_m_mod % MOD;
                sum_f = (sum_f + contrib) % MOD;
            }

            // Compute term to subtract
            long pow_M_K = (K == 0) ? 1 : powerMod(M, K);
            long term = pow_M_K;
            if (M_mod == 1) {
                term = term * powerMod(M, 1) % MOD;
            } else {
                term = term * 1 % MOD;
            }
            long add_val = (1 + M) % MOD;
            term = term * add_val % MOD;

            // Subtract term
            sum_f = (sum_f - term) % MOD;
            if (sum_f < 0) {
                sum_f += MOD;
            }

            System.out.println(sum_f);
        }
        sc.close();
    }
}

JavaScript solution:
var fs = require("fs");
// https://gist.github.com/simonlindholm/38e1a3ff5d99fdbceda541f112f9daf3
var Kattio = {
    _buf: Buffer.alloc(1 << 14),
    _bufPos: 0,
    _bufLen: 0,
    _ensure: function() {
        if (this._bufPos === this._bufLen) {
            this._bufPos = 0;
            this._bufLen = fs.readSync(0, this._buf, 0, this._buf.length, null);
        }
    },
    _isws: function(ch) {
        return ch === 32 || ch === 9 || ch === 10 || ch === 13;
    },
    _islf: function(ch) {
        return ch === 10 || ch === 13;
    },
    _peekChar: function() {
        this._ensure();
        return this._bufPos === this._bufLen ? 0 : this._buf[this._bufPos];
    },
    _skipWs: function() {
        while (this._isws(this._peekChar()))
            this._bufPos++;
    },
    _readUntil: function(stop) {
        this._ensure();
        if (this._bufPos === this._bufLen)
            throw new Error("eof");
        var start = this._bufPos;
        var before = null;
        for (;;) {
            if (this._bufPos === this._bufLen) {
                // Hit the end; need to switch buffers. Thus, stash away all we have so far
                // into the 'before' buffer.
                var len = this._bufPos - start, preLen = (before ? before.length : 0);
                var nbuf = Buffer.alloc(len + preLen);
                if (before)
                    before.copy(nbuf);
                before = nbuf;
                this._buf.copy(before, preLen, start);
                this._ensure();
                start = this._bufPos;
            }
            if (this._bufPos === this._bufLen || stop(this._buf[this._bufPos])) break;
            this._bufPos++;
        }
        if (!before)
            return this._buf.toString("utf8", start, this._bufPos);
        var after = this._buf.slice(start, this._bufPos);
        var res = Buffer.alloc(before.length + after.length);
        before.copy(res);
        after.copy(res, before.length);
        return res.toString();
    },

    nextToken: function() {
        this._skipWs();
        return this._readUntil(this._isws);
    },

    nextLine: function() {
        var line = this._readUntil(this._islf);
        if (this._peekChar() === 13) this._bufPos++;
        if (this._peekChar() === 10) this._bufPos++;
        return line;
    },

    nextNumber: function() { return +this.nextToken(); },
    nextInt: function() { return this.nextToken()|0; }
};

const MOD = 998244353
const MOD_CUT = ((1 << 20) * (1 << 20)) % MOD
function add(a, b) {
    return (a + b) % MOD
}
function minus(a, b) {
    return add(add(a, -b), MOD)
}
function mul(a, b) {
    let r = (a >> 20) * (b >> 20) * MOD_CUT
        + (a & 0xfff00000) * (b & 0xfffff)
        + (a & 0xfffff) * b
    return r % MOD
}
function pow(a, b) {
    let r = 1
    let base = a
    while (b) {
        if (b & 1) {
            r = mul(r, base)
        }
        b >>= 1 // change to divide if b > 1e9 !!
        base = mul(base, base)
    }
    return r
}

const ds = pre(2e5)
function pre(n) {
    const ds = Array(n + 1).fill(0)
    for (let i = 1; i <= n; i++) {
        for (let j = i; j <= n; j += i) {
            ds[j]++
        }
    }
    return ds
}

let t = Kattio.nextNumber()
while (t--) console.log(solve())

function solve() {
    const n = Kattio.nextNumber()
    const m = Kattio.nextNumber()
    const p = Math.floor(n / 2)
    //
    const dp = Array(m)
    const mp = pow(m, p)
    let ans = 0
    for (let g = m - 1; g >= 1; g--) {
        let temp = m
        for (let d = g; d < m; d += g) {
            temp = add(temp, 2 * (m - d))
        }
        // console.log([g, temp])
        temp = pow(temp, p)
        //
        for (let j = g + g; j < m; j += g) {
            temp = minus(temp, dp[j])
        }
        temp = minus(temp, mp)
        //
        dp[g] = temp
        //
        temp = mul(temp, ds[g])
        ans = add(ans, temp)
    }
    // console.log(dp)
    // console.log(ds.slice(0, m))
    ans = minus(ans, mp)
    if (n & 1) ans = mul(ans, m)
    return ans
}

Python solution:
MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N = int(input[ptr])
        M = int(input[ptr+1])
        ptr += 2
        
        # Compute palindromic_count
        k_palin = (N + 1) // 2
        palindromic_count = pow(M, k_palin, MOD)
        
        K = N // 2
        d = N % 2
        M_pow_d = pow(M, d, MOD)
        
        total_sum = 0
        for X in range(1, M + 1):
            q = M // X
            sum_squares = M * (2 * q + 1) - X * q * (q + 1)
            sum_squares %= MOD
            # Compute sum_squares^K mod MOD
            pow_sum = pow(sum_squares, K, MOD)
            term = (pow_sum * M_pow_d) % MOD
            total_sum = (total_sum + term) % MOD
        
        # Calculate the final answer
        ans = (total_sum - palindromic_count * (M + 1)) % MOD
        if ans < 0:
            ans += MOD
        print(ans)

if __name__ == "__main__":
    main()

Ruby solution:
MOD = 998244353

def pow_mod(a, b, mod)
  result = 1
  a = a % mod
  while b > 0
    if b.odd?
      result = result * a % mod
    end
    a = a * a % mod
    b >>= 1
  end
  result
end

def main
  input = $stdin.read.split.map(&:to_i)
  ptr = 0
  test_cases = input[ptr]
  ptr += 1
  results = []
  
  test_cases.times do
    n = input[ptr]
    m = input[ptr + 1]
    ptr += 2
    
    k_palin = (n + 1) / 2
    palindromic_count = pow_mod(m, k_palin, MOD)
    
    k = n / 2
    d = n % 2
    m_pow_d = pow_mod(m, d, MOD)
    
    total_sum = 0
    (1..m).each do |x|
      q = m / x
      term1 = (2 * q + 1) % MOD
      term1 = (m % MOD) * term1 % MOD
      term2 = (x % MOD) * q % MOD
      term2 = term2 * (q + 1) % MOD
      sum_squares = (term1 - term2) % MOD
      sum_squares += MOD if sum_squares < 0
      
      pow_sum = pow_mod(sum_squares, k, MOD)
      term = pow_sum * m_pow_d % MOD
      total_sum = (total_sum + term) % MOD
    end
    
    ans = (total_sum - palindromic_count * (m + 1) % MOD) % MOD
    ans += MOD if ans < 0
    results << ans
  end
  
  puts results.join("\n")
end

main