给出K和N,求 ,N,K < 109。
数据如此BT,从1到N穷举是不可能的。不妨列出小规模时的情况。比如N = 5,K = 5。
5%5=0 5/5=1
5%4=1 5/4=1
5%3=2 5/3=1
5%2=1 5/2=2
5%1=0 5/1=5
可以看到当商相同时,余数成等差数列,这是题目的关键。所以我们可以穷举商,计算等差数列之和。
#include <cstdio>
#include <string>
int N, K, l[20];
void proc ();
int main ()
...{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d%d", &N, &K ) == 2 )
...{
proc ();
}
return 0;
}
void addm ( int a[], int x, int y )
...{
int i, j; // 这题数据太bt,高精度乘法= =
int lx[10], ly[10],
sx, sy; // 长度
for ( i = 0; i < 10; i ++, x /= 10 )
...{
lx[i] = x % 10;
if ( x == 0 )
...{
sx = i;
break;
}
}
for ( j = 0; j < 10; j ++, y /= 10 )
...{
ly[j] = y % 10;
if ( y == 0 )
...{
sy = j;
break;
}
}
for ( i = 0; i < sx; i ++ )
...{
for ( j = 0; j < sy; j ++ )
...{
a[i + j] += lx[i] * ly[j];
}
}
int c = 0, t;
for ( i = 0; i < 20; i ++ )
...{
t = a[i] + c;
a[i] = t % 10, c = t / 10;
}
}
void print ( int a[] )
...{
int i;
for ( i = 20; i >= 0; i -- )
if ( a[i] )
break;
if ( i == -1 )
...{
printf ( "0 " );
return;
}
for ( ; i >= 0; i -- )
printf ( "%d", a[i] );
printf ( " " );
}
void proc ()
...{
int d; // 商
memset ( l, 0x00, sizeof ( l ) );
int L = 0;
if ( N < 10000 )
...{
for ( d = 1; d <= N; d ++ )
L += K % d;
printf ( "%d ", L );
return;
}
// z = k / i
if ( K < N )
d = 1;
else
d = K / N;
int low, high, first = 1;
for ( ; d * d <= K; d ++ )
...{
high = K / d, low = K / ( d + 1 ) + 1;
if ( N < K && first )
high = N, first = 0;
int x = high - low + 1;
low = K % low;
high = K % high;
int y = high + low;
//sum += double ( x ) * double ( high + low ) / 2;
if ( x % 2 == 0 )
x /= 2;
else
y /= 2;
addm ( l, x, y );
}
//printf ( "%.0f ", sum );
low = K / d;
for ( ; low >= 2; low -- )
//sum += K % low;
addm ( l, K % low, 1 );
if ( K < N )
//sum += double ( K ) * double ( N - K );
addm ( l, K, N - K );
print ( l );
}
#include <string>
int N, K, l[20];
void proc ();
int main ()
...{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d%d", &N, &K ) == 2 )
...{
proc ();
}
return 0;
}
void addm ( int a[], int x, int y )
...{
int i, j; // 这题数据太bt,高精度乘法= =
int lx[10], ly[10],
sx, sy; // 长度
for ( i = 0; i < 10; i ++, x /= 10 )
...{
lx[i] = x % 10;
if ( x == 0 )
...{
sx = i;
break;
}
}
for ( j = 0; j < 10; j ++, y /= 10 )
...{
ly[j] = y % 10;
if ( y == 0 )
...{
sy = j;
break;
}
}
for ( i = 0; i < sx; i ++ )
...{
for ( j = 0; j < sy; j ++ )
...{
a[i + j] += lx[i] * ly[j];
}
}
int c = 0, t;
for ( i = 0; i < 20; i ++ )
...{
t = a[i] + c;
a[i] = t % 10, c = t / 10;
}
}
void print ( int a[] )
...{
int i;
for ( i = 20; i >= 0; i -- )
if ( a[i] )
break;
if ( i == -1 )
...{
printf ( "0 " );
return;
}
for ( ; i >= 0; i -- )
printf ( "%d", a[i] );
printf ( " " );
}
void proc ()
...{
int d; // 商
memset ( l, 0x00, sizeof ( l ) );
int L = 0;
if ( N < 10000 )
...{
for ( d = 1; d <= N; d ++ )
L += K % d;
printf ( "%d ", L );
return;
}
// z = k / i
if ( K < N )
d = 1;
else
d = K / N;
int low, high, first = 1;
for ( ; d * d <= K; d ++ )
...{
high = K / d, low = K / ( d + 1 ) + 1;
if ( N < K && first )
high = N, first = 0;
int x = high - low + 1;
low = K % low;
high = K % high;
int y = high + low;
//sum += double ( x ) * double ( high + low ) / 2;
if ( x % 2 == 0 )
x /= 2;
else
y /= 2;
addm ( l, x, y );
}
//printf ( "%.0f ", sum );
low = K / d;
for ( ; low >= 2; low -- )
//sum += K % low;
addm ( l, K % low, 1 );
if ( K < N )
//sum += double ( K ) * double ( N - K );
addm ( l, K, N - K );
print ( l );
}