BZOJ 4173 数论

思路：

$(m％k+n％k>=k) *phi(k)$

$我们不妨设n=q_1k+r_1　m=q_2k+r$2

$n+m=(q_1+q_2)k+r1+r2$

${\lfloor}\frac{n+m}{k}{\rfloor}-{\lfloor}\frac{m}{k}{\rfloor}-{\lfloor}\frac{n}{k}{\rfloor}=(m％k+n％k>=k)$

$原式=phi(k)*({\lfloor}\frac{n+m}{k}{\rfloor}-{\lfloor}\frac{m}{k}{\rfloor}-{\lfloor}\frac{n}{k}{\rfloor})$

$id=phi|1$

$n=\Sigma_{d|n}phi(d)$

$原式=\Sigma_{i=1}^{n+m}i-\Sigma_{i=1}^mi-\Sigma_{i=1}^ni$
$　　=(n+m)*(n+m-1)/2+m*(m-1)/2+n*(n-2)/2$
$　　=n*m$

//By SiriusRen

#include <cstdio>

using namespace std;

typedef long long ll;

ll n,m,mod=;

ll phi(ll x){

    ll res=;

    for(int i=;1LL*i*i<=x;i++){

        if(x%i==){

            while(x%i==)x/=i,res=res*i;

            res=res/i*(i-);

        }

    }if(x!=)res=res*(x-);

    return res;

}

int main(){

    scanf("%lld%lld",&n,&m);

    printf("%lld\n",((((phi(n)%mod)*(phi(m)%mod))%mod*(n%mod))%mod*(m%mod))%mod);

}

巴特西

BZOJ 4173 数论

最新文章

热门文章