# 9 条题解

• @ 2018-03-28 21:48:31

反演裸题，乱搞就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool pd[200005];
ll p[200005],mu[200005],s[200005];
ll f[200005];
void getmu(int n){
ll ps=0; mu[1]=1;
for (ll i=2;i<=n;i++){
if (pd[i]==0) mu[i]=-1,ps++,p[ps]=i;
for (ll j=1;j<=ps;j++){
if (i*p[j]>n) break;
pd[i*p[j]]=1;
if (i%p[j]==0){
mu[i*p[j]]=0; break;
}
mu[i*p[j]]=-mu[i];
}
}
s[0]=0;
for (ll i=1;i<=n;i++)
s[i]=mu[i]+s[i-1];
}
ll fy(int n,int m,int d){
ll ans=0;
n/=d; m/=d;
for (int i=1;i<=n;i){
int las=min(n/(n/i),m/(m/i));
ans+=(s[las]-s[i-1])*(n/i)*(m/i);
i=las+1;
}
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
memset(pd,0,sizeof(pd));
getmu(m);
for (int i=1;i<=n;i++){
f[i]=fy(n,m,i);
}
ll ans=0;
for (int i=1;i<=n;i++){
ans+=2*(i-1)*f[i]+f[i];
}
printf("%lld\n",ans);
return 0;
}

• @ 2017-04-10 10:10:13
• @ 2018-08-18 16:45:16

注意计算出来的中间结果的类型，否则最后一个测试点会溢出。

#include <stdio.h>

long long f[100001];
long long n, m;

int main()
{
long long mx;
int i, j;
long long ans = 0;
scanf("%lld%lld", &n, &m);
if (n > m) mx = m;
else mx = n;
for (i = mx; i >= 1; i--) {
f[i] = (n / i) * (m / i);
for (j = i * 2; j <= mx; j += i) {
f[i] -= f[j];
}
}
for (i = 1; i <= mx; i++) {
ans += f[i] * (2 * i - 1);
}
printf("%lld", ans);
return 0;
}

• @ 2016-11-09 20:17:22
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn =100005;
typedef long long LL ;
LL f[maxn];
int main() {
int n,m;
scanf("%d%d",&n,&m);
LL t=min(n,m);
LL ans=0;
for(int i=t; i; i--) {
f[i]=(LL)(m/i)*(n/i);
for(int j=i+i; j<maxn; j+=i)
f[i]-=f[j];
ans+=f[i]*(2*i-1); }
printf("%lld\n",ans);
return 0; }

• @ 2016-02-12 18:35:14
• @ 2015-09-09 22:51:08

测试数据 #0: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 1292 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 1296 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #5: Accepted, time = 1 ms, mem = 1292 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #9: Accepted, time = 18 ms, mem = 1292 KiB, score = 10

Accepted, time = 79 ms, mem = 1296 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

inline long long min( long long a , long long b )
{
if( a > b )
return b;
return a;
}

long long f[100000 + 2];
long long n , m;
long long ans;
long long i , j;

int main()
{
scanf( "%d %d" , &n , &m );
for( i = min( n , m ) ; i >= 1 ; i-- )
{
f[i] = ( n / i ) * ( m / i );
for( j = 2 * i ; j <= min( n , m ) ; j += i )
f[i] -= f[j];
}
for( i = min( n , m ) ; i >= 1 ; i-- )
ans += f[i] * ( 2 * i - 1 );
cout << ans << endl;
return 0;
}
水题

• @ 2014-06-10 15:54:37

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define ll long long
#define Sum( l , r ) ( sum[ r ] - sum[ l - 1 ] )
#define maxn 100100

bool f[ maxn ] ;
int u[ maxn ] , n , m , sum[ maxn ] ;
ll ans = 0 ;

void Init( ) {
memset( f , true , sizeof( f ) ) ;
f[ 0 ] = f[ 1 ] = false , u[ 1 ] = 1 ;
for ( int i = 1 ; i ++ < min( n , m ) ; ) if ( f[ i ] ) {
u[ i ] = - 1 ;
for ( int j = i << 1 ; j <= min( n , m ) ; j += i ) {
f[ j ] = false ;
if ( ! ( ( j / i ) % i ) ) u[ j ] = 0 ; else u[ j ] = u[ j / i ] * - 1 ;
}
}
sum[ 0 ] = 0 ;
for ( int i = 0 ; i ++ < min( n , m ) ; ) sum[ i ] = sum[ i - 1 ] + u[ i ] ;
}

ll query( int a , int b ) {
ll ret = 0 ;
for ( int i = 1 ; i <= min( a , b ) ; ) {
int pos = min( a / ( a / i ) , b / ( b / i ) ) ;
ret += ( ll )( Sum( i , pos ) ) * ( ll )( a / i ) * ( ll )( b / i ) ;
i = pos + 1 ;
}
return ret ;
}

int main( ) {
scanf( "%d%d" , &n , &m ) ;
Init( ) ;
for ( int i = 0 ; i ++ < min( n , m ) ; ) {
ans += ( ll )( i ) * query( n / i , m / i ) * 2 ;
}
ans -= ( ll )( n ) * ( ll )( m ) ;
printf( "%lld\n" , ans ) ;
return 0 ;
}

• @ 2014-06-27 20:22:53

80分很开心了~~~~~~
直接二维n,m然后gcd（n,m),此次能量损失为sqr(gcd(n,m)),并且把斜率记入（相当于已经算了这条线上所有的损失了）

• @ 2013-05-19 00:07:05

最简单朴素竟然能得80分！

• 1

ID
1732

5

425

145

34%

3