小凯的数字

逆元 $9$ 的性质

分析：

因为一个数字对 $9$ 取模等于其各位数字之和对 $9$ 取模。那么这里问题转化为了 $[l,r]$ 区间的数字和输出对 $9$ 取模的结果。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=9;
//s函数求的是[1,x]的数字mod 9 的和 
int s(int x)
{
    int n=x/9,m=x%9;
    int s1=n*36;//[1,9]的完整块%9的和是36 
    int s2=m*(m+1)/2;//[1,m]这个等差数列的和
    //剩余的数字是从1开始的，因为mod 9   
    return s1+s2; 
}
void solve()
{
    int l,r;
    cin>>l>>r;
    cout<<((s(r)-s(l-1))%mod)<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

模意义下的乘法逆元

分析：

求 $[1,n] mod p$ 的乘法逆元(这里的模数p是质数)。因为 $1$ 的逆元就是其本身，$ a[i] = (p - p / i) \times a[p \% i] \mod p $

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
long long a[N];
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    a[1]=1;

    for(int i=2;i<=n;i++)
    {
    a[i]=(p-p/i)*a[p%i]%p;  
    }

    for(int i=1;i<=n;i++)
    printf("%lld\n",a[i]);
    return 0;
}