Java(javac 1.8) 解法, 执行用时: 4728ms, 内存消耗: 116728K, 提交时间: 2020-12-22 14:31:01

import java.util.Scanner;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        int T = stdin.nextInt();
        while (T > 0) {
            T--;
            long n = stdin.nextLong(), mod = stdin.nextLong(), m = (long) Math.sqrt(n);
            if(m*m > n)m--;
            n %= mod;
            long sum = (n + 1) % mod * n % mod * 3 % mod;
            long sub = m % mod * (m + 1) % mod * (2 * m + 1) % mod;
            System.out.println((sum - sub + mod) % mod);
        }
        stdin.close();
    }
}

C++(clang++11) 解法, 执行用时: 452ms, 内存消耗: 32380K, 提交时间: 2020-12-21 22:07:22

#include <stdio.h>
#include <math.h>
int main()
{
	int T;
	long long n,m,mod;
	int i;
	long long ans,tmp;
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%lld%lld",&n,&mod);
		m=sqrt(n);
		if((m+1)*(m+1)<=n)m++;
		if(m*m>n)m--;
		n%=mod;
		m%=mod;
		n=(3*n*(n+1))%mod;
		tmp=(m*(m+1))%mod;
		m=(tmp*(2*m+1)%mod)%mod;
		ans=(n-m+mod)%mod;
		printf("%lld\n",ans);
	}
}

pypy3(pypy3.6.1) 解法, 执行用时: 4501ms, 内存消耗: 36236K, 提交时间: 2020-12-19 13:33:02

import math
t=int(input())
while(t):
    a=input().split()
    x=math.floor(math.sqrt(int(a[0])))
    if x*x>int(a[0]):
        x-=1

    n=int(a[0])
    ans=(n+1)*n//2-x*(x+1)*(2*x+1)//6
    print(ans*6%(int(a[1])))
    t-=1