欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

「BZOJ4173」数学

程序员文章站 2022-05-29 07:56:16
题面 已知 $$\large{S(n,m)=\{k_{1},k_{2},\cdots k_{i}\}}$$ 且每个 $k$ 满足 $$\large{n \%k+m\%k\geq k}$$ 求 $$\large{\phi(n)\times \phi(m)\times\sum_{k\in S(n,m) ......

题面

已知

\[\large{s(n,m)=\{k_{1},k_{2},\cdots k_{i}\}}\]

且每个 \(k\) 满足

\[\large{n \%k+m\%k\geq k}\]

\[\large{\phi(n)\times \phi(m)\times\sum_{k\in s(n,m) }\phi(k)\%998244353}\]

part 1

\[\large{n=a_{1} \times k +b_{1} ,m=a_{2} \times k +b_{2}}\]

所以有

\[\large{b_{1}+b_{2} \geq k}\]

\[\large{(a_{1} \times k +b_{1})+(a_{2} \times k +b_{2}) \geq (a_{1}+a_{2}+1)\times k}\]

所以

\[\large{n+m \geq (a_{1}+a_{2}+1)\times k}\]

两边同时除以 \(k\) 并向下取整得

\[\large{\lfloor \frac{n+m}{k} \rfloor \geq a_{1}+a_{2}+1}\]

因为

\[\large{a_{1}=\lfloor \frac{n}{k} \rfloor ,a_{2}=\lfloor \frac{m}{k} \rfloor}\]

所以

\[\large{\lfloor \frac{n+m}{k} \rfloor \geq \lfloor \frac{n}{k} \rfloor+\lfloor \frac{m}{k} \rfloor+1}\]

\[\large{\lfloor \frac{n+m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor - \lfloor \frac{m}{k} \rfloor\geq 1}\]

已知

\[\large{\lfloor\frac{x}{y}\rfloor=\frac{x}{y}-\{\frac{x}{y}\}}\]

所以式子可化为

\[\large{\frac{n+m}{k}-\{\frac{n+m}{k}\}-(\frac{n}{k}-\{\frac{n}{k}\}+\frac{m}{k}-\{\frac{m}{k}\})} \geq 1\]

化简得

\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}\geq 1\]

因为

\[\large{0\leq\{\frac{n}{k}\}},\{\frac{m}{k}\},\{\frac{n+m}{k}\}<1\]

所以

\[\large{1<\{\frac{n}{k}\}}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}<2\]

又因为

\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}\geq 1,\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}\in n^{+}\]

所以

\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}= 1\]

\[\large{\lfloor \frac{n+m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor - \lfloor \frac{m}{k} \rfloor= 1}\]

part2

先忽视要求式子的部分, 得

\[\large{\sum_{k\in s(n,m)}\phi(k)}\]

\[\large{\sum_{n \%k+m\%k\geq k }\phi(k)}\]

\[\large{\sum_{k=1}^{n+m}\phi(k)\times\lfloor \frac{n+m}{k} \rfloor}-\sum_{k=1}^{n}\phi(k)\times\lfloor \frac{n}{k} \rfloor-\sum_{k=1}^{m}\phi(k)\times\lfloor \frac{m}{k} \rfloor\]

因为

\[\large{n=\sum_{d|n}\phi(d)}\]

所以

\[\large{\sum_{i=1}^{n+m}i-\sum_{i=1}^{n}i-\sum_{i=1}^{m}i=\frac{(n+m)\times(n+m-1)}{2}-\frac{n\times(n-1)}{2}-\frac{m\times(m-1)}{2}-}\]

\[\large{=n\times m}\]

结论

\[\large{ans=\large{\phi(n)\times \phi(m)\times n\times m\%998244353}}\]

代码

#include <bits/stdc++.h>
using namespace std;

const int mod=998244353;

unsigned long long n,m;

unsigned long long phi(unsigned long long x)
  {
    unsigned long long ans=x;
    for (unsigned long long i=2;i*i<=x;i++)
      {
        if (x%i==0)
          {
            ans-=ans/i;
            while (x%i==0) x/=i;
          }
      }
    if (x>1) ans-=ans/x;
    return ans%mod;
  }

int main()
  {
    cin>>n>>m;
    cout<<(phi(n)%mod)*(phi(m)%mod)%mod*(n%mod)%mod*(m%mod)%mod;
    return 0;
  }