[51Nod 1227] 평균 최소 공배수 - 두 교 체

테스트 주소: 평균 최소 공배수 방법: 이 문 제 는 두 교 체 를 사용 해 야 합 니 다.이 문 제 를 푸 는 과정 은 비교적 전형 적 이 고 두 교 체 를 만 드 는 데 더욱 어 려 운 기초 이다.
다음 에 사용 할 기호 와 함 수 를 먼저 정의 합 니 다: 멱 함수: idk (n) = nk (완전 적) lcm (i, j) 와 gcd (i, j): i 와 j 의 최소 공배수 와 최대 공약수 (이것 을 모 르 면.))[S]: 만약 식 S 가 진짜 라면 [S] = 1, 그렇지 않 으 면 [S] = 0.
우 리 는 공식 적 으로 요구 하 는 함 수 를 표현 한다. A (n) = 1n ∑ ni = 1lcm (n, i), F (n) = ∑ ni = 1A (i) 를 구한다.A 는 적 함수 가 아니 기 때문에 우 리 는 식 을 적 함수 접두사 와 형식 으로 바 꾸 는 방법 을 생각해 야 한다.우 리 는 lcm (i, j) 를 안다.×gcd (i, j) = ij, 그래서 A (n) = 1n ∑ ni = 1nigcd (n, i) = ∑ ni = 1igcd (n, i).그러나 igcd (n, i) 는 여전히 적 극적인 것 이 아니 기 때문에 우 리 는 더욱 간소화 합 니 다.
A(n)=∑i=1nigcd(n,i)=∑i=1n∑d|n[gcd(n,i)=d]×id=∑d|n∑id=1nd[gcd(nd,id)=1]×id
알아차리다
∑n/di/d=1[gcd(nd,id)=1]×id 는 사실 작 게 물 어 보 는 것 과 같 습 니 다.
하면, 만약, 만약...
i 와
그러면
x - i 도
x. 상호 질 (이것 은 매우 분명 하 다. 마음대로 증 거 를 증명 하면 된다) 은
x 의 와
x. 상호 질 적 인 수 는 쌍 을 이 루어 나타 나 는 것 이 고 모든 쌍 의 공헌 은
x, 그래서 이하
x 의 와
x. 상호 질의 수의 합 은?
x×φ(x)×12. 특히
1 의 와
1. 상호 질의 수의 합 은?
1 (위 공식 으로 계산 하면 산출
12), 위의 식 에 대 입 하면:
A(n)=12(1+∑d|nd×φ(d))
우 리 는 이 식 이 이미 약간 적 함수 의 뜻 이 있다 는 것 을 발견 했다. 우 리 는 다시 이 식 으로 계산한다.
F(n) ：
F(n)=∑i=1nA(i)=12(n+∑i=1n∑d|id×φ(d))=12(n+∑i=1n∑d=1⌊ni⌋d×φ(d))
그렇게
G(n)=∑ni=1i×φ(i) 적 함수 접두사 가 합 쳐 진 것 입 니 다.
요구 함수
id⋅φ 접두사 와 접 두 사 를 잘 계산 하 는 함 수 를 고려 하여 접두사 와 함 수 를 잘 계산 할 수 있 습 니 다.분명히
(id⋅φ)∗ id = id2, 왜냐하면
∑d|nd×φ(d)×nd=n∑d|nφ(d) = n2, 그러면:
n(n+1)(2n+1)6=∑i=1ni2=∑i=1n∑d|id×φ(d)×id=∑id=1nid∑d=1⌊nid⌋d×φ(d)=∑i=1ni×G(⌊ni⌋)
상술 한 식 을 이해 하지 못 하 는 학우 들 은 약수, 배수 와 공헌 방면 에서 이해 해 볼 수 있다.
장차
G (n) 하 나 를 꺼 내 면:
G(n)=n(n+1)(2n+1)6−∑i=2ni×G(⌊ni⌋)
이 식 을 결합 합 니 다:
F(n)=12(n+∑i=1nG(⌊ni⌋))
이렇게 하면 두 교 체 를 사용 하여 계산 할 수 있 습 니 다. 하 쉬 표 로 무 게 를 판단 하고 미리 처리 할 수 있 습 니 다.
n23 개
G 값, 도달 할 수 있 습 니 다.
O (n23) 의 시간 복잡 도 입 니 다.
109 + 7, 그래서 결 과 를 직접 곱 할 수 없습니다.
12. 타 야 합 니 다.
2. 모델 에 대하 여
109 + 7 의 역 원:
5×108+4 。
다음은 본인 코드 입 니 다.

#include 
#include 
#include 
#include 
#include 
#define hashsize 5000000
#define limit 1000000
#define mod 1000000007
#define ll long long
using namespace std;
ll a,b,phi[limit+5],sum[limit+5],h[hashsize+5]={0},f[hashsize+5];
bool prime[limit+5]={0};

int hash(ll x)
{
  ll s=x%hashsize;
  while(h[s]&&h[s]!=x) s=(s+1)%hashsize;
  return s;
}

void init()
{
  for(int i=1;i<=limit;i++) phi[i]=i;
  for(ll i=2;i<=limit;i++)
    if (!prime[i])
    {
      for(ll j=1;i*j<=limit;j++)
      {
        prime[i*j]=1;
        phi[i*j]=phi[i*j]/i*(i-1);
      }
    }
  sum[0]=0;
  for(int i=1;i<=limit;i++)
    sum[i]=(sum[i-1]+i*phi[i])%mod;
}

ll gcd(ll a,ll b)
{
  return (b==0)?a:gcd(b,a%b);
}

ll sum1(ll a,ll b)
{
  return (b*(b+1)/2-a*(a-1)/2)%mod;
}

ll sum2(ll x)
{
  ll a=x,b=x+1,c=2*x+1,s=6,g;
  g=gcd(a,s),a/=g,s/=g;
  g=gcd(b,s),b/=g,s/=g;
  g=gcd(c,s),c/=g,s/=g;
  return (((a*b)%mod)*c)%mod;
}

ll G(ll x)
{
  if (x<=limit) return sum[x];
  int pos=hash(x);
  if (h[pos]==x) return f[pos];
  ll i=2,next,s=0;
  while(i<=x)
  {
    next=x/(x/i);
    s=(s+sum1(i,next)*G(x/i))%mod;
    i=next+1;
  }
  h[pos]=x,f[pos]=(sum2(x)-s+mod)%mod;
  return f[pos];
}

ll F(ll x)
{
  ll i=1,next,s=0;
  while(i<=x)
  {
    next=x/(x/i);
    s=(s+(next-i+1)*G(x/i))%mod;
    i=next+1;
  }
  return (500000004*(s+x))%mod;
}

int main()
{
  init();
  scanf("%lld%lld",&a,&b);
  printf("%lld",(F(b)-F(a-1)+mod)%mod);

  return 0;
}