我看讨论区里好像也没有跟我错的一样的啊/kel

求助路过大佬：

#include <iostream>
#include <map>
using namespace std ;

#define int long long
const int N = 1e7 ;
int M , n , phi[N+5] , p[N+5] , c , ans , inv2 ;
bool vis[N+5] ;
map < int , int > val ;

inline int qpow ( int x , int y ) {
	int res = 1 ;
	while ( y ) {
		if ( y & 1 ) res = res * x % M ;
		x = x * x % M ;
		y >>= 1 ;
	}
	return res ;
}

inline int w2 ( int x ) {
	x = x % M ;
//	int t = x * ( x + 1 ) % M * inv2 % M ;
	int t = x * ( x + 1 ) / 2 % M ;
	return t * t % M ;
}

int solve ( int x ) {
	if ( x < N )
		return phi [ x ] ;
	if ( val [ x ] )
		return val [ x ] ;
	int res = w2 ( x ) ;
	for ( int l = 2 , r ; l <= x ; l = r + 1 ) {
		r = x / ( x / l ) ;
		res = ( res - ( w2 ( r ) - w2 ( l - 1 ) ) * solve ( x / l ) % M ) % M ;
	}
	val [ x ] = res = ( res + M ) % M ;
	return res ;
}

signed main ( ) {
	cin >> M >> n ;
	inv2 = qpow ( 2 , M - 2 ) ;
	phi [ 1 ] = 1 ;
	for ( int i = 2 ; i < N ; ++ i ) {
		if ( ! vis [ i ] ) {
			p [ ++ c ] = i ;
			phi [ i ] = i - 1 ;
		}
		for ( int j = 1 ; j <= c && i * p [ j ] < N ; ++ j ) {
			vis [ i * p [ j ] ] = 1 ;
			if ( i % p [ j ] == 0 ) {
				phi [ i * p [ j ] ] = phi [ i ] * p [ j ] % M ;
				break ;
			}
			phi [ i * p [ j ] ] = phi [ i ] * ( p [ j ] - 1 ) % M ;
		}
	}
	for ( int i = 1 ; i < N ; ++ i )
		phi [ i ] = ( i * i % M * phi [ i ] % M + phi [ i - 1 ] ) % M ;
	for ( int l = 1 , r ; l <= n ; l = r + 1 ) {
		r = n / ( n / l ) ;
		ans = ( ans + w2 ( n / l ) * ( solve ( r ) - solve ( l - 1 ) ) % M ) % M ;
	}
	ans = ( ans + M ) % M ;
	cout << ans << "\n" ;
	return 0 ;
}