[CQOI 2017] bzoj 4815 작은 Q 의 표

서로 영향 을 주 는 것 은 gcd 와 같은 숫자 라 는 것 을 알 수 있다.또한 조건 2 에 따라 모든 gcd 의 같은 수의 비율 은 변 하지 않 을 것 임 을 알 수 있 습 니 다. 또한 처음에 a (x, y) = xy 는 한 조 의 해 이기 때문에 매번 작업 할 때마다 모든 gcd 의 같은 수 를 a (x, y) = kxy 로 수정 하 는 것 과 같 습 니 다.따라서 수정 에 대해 서 는 f (d) 를 유지 하기 만 하면 모든 gcd (x, y) = d 의 (x, y) 에 a (x, y) = f (d) * 8727 ° xy 가 있 음 을 표시 합 니 다.다음은 질문 을 고려 해 보 자.
====∑i=1n∑j=1nf(gcd(i,j))∗ij∑d=1nf(d)∑i=1n∑j=1nij∗[gcd(i,j)=d]∑d=1nf(d)∗d2∑i=1⌊nd⌋∑j=1⌊nd⌋ij∗e(gcd(i,j))∑d=1nf(d)∗d2∑i=1⌊nd⌋∑j=1⌊nd⌋ij∑x|i,x|jμ(x)∑d=1nf(d)∗d2∑x=1⌊nd⌋μ(x)x2∑i=1⌊ndx⌋∑j=1⌊ndx⌋ij
적다
s(n)=∑i=1ni=n(n+1)2
g(n)=∑i=1nμ(i)∗i2∗s2(⌊ni⌋)
하면, 만약, 만약...
g. 다음 함수 로 블록 을 나 누 어 원 문 제 를 풀 수 있 습 니 다.근 데 바로 순서대로 하면...
O (N √) 의 것 은 받 아들 일 수 없다.고려 하 다알아차리다
활용 단어 참조
⌊ n − 1d ⌋ 大
1. 물론
d | n, 즉
나 누 기
d 나머지 는 0 이다.그래서 얻 을 수 있다.
g(n)=g(n−1)+∑i|nμ(i)∗i2(s2(ni)−s2(ni−1))=g(n−1)+n3∑i|nμ(i)∗1i
그 속
h(n)=∑i|nμ(i) 8727i 는 적 함수 로 선형 체 를 할 수 있 기 때문에 우 리 는 할 수 있다.
O (n) 전처리
g 。
또 하나의 문제 가 있 습 니 다. 답 에 대해 다음 함수 블록 을 나 눌 때 유지 해 야 합 니 다.
f (i) * 8727 ° i2 의 접두사 와 트 리 배열 을 직접 사용 하면 수정 은?
O (logn) 의 질문 은?
O (n √ logn) 의 것 은 받 아들 일 수 없다.따라서 블록 을 나 누 어 수정 의 복잡 도 를 희생 하여 문의 의 복잡 도 를 낮 추고 한 번 에 수정 할 수 있다.
O (n √), 단일 질문
O(1) 。이렇게 마지막 복잡 도 는...
O(n+mn√) 。
약간 카드 가 있 는 것 같 아 요. 작은 걸 감안 하면...
d = gcd (x, y) 가 호출 된 횟수 가 비교적 많 습 니 다. 블록 을 나 눌 때 접미사 와 수정 횟수 를 줄 일 수 있 습 니 다.

#include
#include
#include
using namespace std;
#define LL long long
const int p=1000000007,maxn=4000010,maxT=2010;
LL f[maxn],g[maxn],h[maxn],inv[maxn],
sum[maxT],sumin[maxT][maxT];
int prm[maxn],have[maxn],bel[maxn],L[maxT],R[maxT],
q,n,T,tot;
int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}
void pause()
{
    int x;
    x=1;
}
void init()
{
    inv[1]=g[1]=h[1]=1;
    for (int i=2;i<=n;i++)
    {
        inv[i]=(p-inv[p%i])*(p/i)%p;
        if (!have[i])
        {
            prm[++tot]=i;
            h[i]=(1-inv[i]+p)%p;
        }
        for (int j=1;j<=tot&&(LL)i*prm[j]<=n;j++)
        {
            have[i*prm[j]]=1;
            if (i%prm[j]==0)
            {
                h[i*prm[j]]=h[i];
                break;
            }
            else h[i*prm[j]]=h[i]*h[prm[j]]%p;
        }
        g[i]=(g[i-1]+(LL)i*i%p*i%p*h[i])%p;
    }
    T=sqrt(n);
    for (int i=1;i<=T;i++)
    {
        L[i]=R[i-1]+1;
        R[i]=i==T?n:L[i]+T-1;
        for (int j=L[i];j<=R[i];j++)
        {
            f[j]=1;
            bel[j]=i;
            sumin[i][j-L[i]+1]=(sumin[i][j-L[i]]+(LL)j*j)%p;
        }
    }
    for (int i=T;i;i--)
        sum[i]=(sum[i+1]+sumin[i][R[i]-L[i]+1])%p;
}
LL getsum(int l,int r)
{
    //if (l==10&&r==13) pause();
    //LL ret1;
    int x=bel[l],y=bel[r];
    if (x==y) return (sumin[x][r-L[x]+1]-sumin[x][l-L[x]]+p)%p;
    return (sum[x+1]-sum[y]+p+sumin[y][r-L[y]+1]+sumin[x][R[x]-L[x]+1]-sumin[x][l-L[x]]+p)%p;
    /*LL ret=0;
    for (int i=l;i<=r;i++) ret=(ret+f[i]*i%p*i%p)%p;
    if (ret!=ret1) pause();
    return ret;*/
}
void update(int d)
{
    for (int j=d;j<=R[bel[d]];j++)
        sumin[bel[d]][j-L[bel[d]]+1]=(sumin[bel[d]][j-L[bel[d]]]+f[j]*j%p*j)%p;
    for (int j=bel[d];j;j--)
        sum[j]=(sum[j+1]+sumin[j][R[j]-L[j]+1])%p;
}
void solve(int m)
{
    LL ans=0;
    int u;
    for (int j=1;j<=m;j=u+1)
    {
        u=m/(m/j);
        ans=(ans+getsum(j,u)*g[m/j])%p;
    }
    printf("%lld
",ans);
}
int main()
{
    /*freopen("table.in","r",stdin);
    freopen("table.out","w",stdout);*/
    int xx,yy,m,d;
    LL x;
    scanf("%d%d",&q,&n);
    init();
    while (q--)
    {
        scanf("%d%d%lld%d",&xx,&yy,&x,&m);
        x%=p;
        d=gcd(xx,yy);
        f[d]=(LL)x*inv[xx]%p*inv[yy]%p;
        update(d);
        solve(m);
    }
}