P3327 [SDOI2015]約數個數和

題意：

設 d(x) 為 x 的約數個數，給定 n,m，求
${\sum }_{i=1}^n{\sum }_{j=1}^{m}d(i,j)$

題解：

代碼：

// Problem: P3327 [SDOI2015]約數個數和 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3327 // Memory Limit: 125 MB // Time Limit: 1000 ms // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug( a, b ) printf( "%s = %d\n", a, b ); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair< int, int > PII; clock_t startTime, endTime; // Fe~Jozky const ll INF_ll = 1e18; const int INF_int = 0x3f3f3f3f; void read(){}; template < typename _Tp, typename... _Tps > void read( _Tp& x, _Tps&... Ar ) {x = 0;char c = getchar();bool flag = 0;while ( c < '0' || c > '9' )flag |= ( c == '-' ), c = getchar();while ( c >= '0' && c <= '9' )x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 ), c = getchar();if ( flag )x = -x;read( Ar... ); } template < typename T > inline void write( T x ) {if ( x < 0 ){x = ~( x - 1 );putchar( '-' );}if ( x > 9 )write( x / 10 );putchar( x % 10 + '0' ); } void rd_test() { #ifdef LOCALstartTime = clock();freopen( "in.txt", "r", stdin ); #endif } void Time_test() { #ifdef LOCALendTime = clock();printf( "\nRun Time:%lfs\n", ( double )( endTime - startTime ) / CLOCKS_PER_SEC ); #endif } const int N = 5e4 + 5; int tot, mu[ N ], p[ N ]; long long s[ N ]; bool vis[ N ];void init() {mu[ 1 ] = 1;for ( int i = 2; i <= 5e4; ++i ){if ( !vis[ i ] )p[ ++tot ] = i, mu[ i ] = -1;for ( int j = 1; j <= tot && i * p[ j ] <= 5e4; ++j ){vis[ i * p[ j ] ] = 1;if ( i % p[ j ] == 0 ){mu[ i * p[ j ] ] = 0;break;}else{mu[ i * p[ j ] ] = -mu[ i ];}}}for ( int i = 1; i <= 5e4; ++i )mu[ i ] += mu[ i - 1 ];for ( int x = 1; x <= 5e4; ++x ){long long res = 0;for ( int i = 1, j; i <= x; i = j + 1 )j = x / ( x / i ), res += 1LL * ( j - i + 1 ) * ( x / i );s[ x ] = res;} } int main() {init();int T;for ( scanf( "%d", &T ); T--; ){int n, m;scanf( "%d%d", &n, &m );if ( n > m )swap( n, m );long long ans = 0;for ( int i = 1, j; i <= n; i = j + 1 ){j = min( n / ( n / i ), m / ( m / i ) );ans += 1LL * ( mu[ j ] - mu[ i - 1 ] ) * s[ n / i ] * s[ m / i ];}printf( "%lld\n", ans );}return 0; }

總結

以上是生活随笔為你收集整理的P3327 [SDOI2015]约数个数和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。