【2018ICPC0沈阳网络赛】 G. Spare Tire

G. Spare Tire
题意
给出a(n)的计算方法为

$$a_n=0\ \ \ n=0$$
$$a_n=2\ \ \ n=1$$
$$a_n=\frac{3a_{n-1}-a_{n-2}}{2}+\ n+1\ \ \ \ n>1$$
$$\ \ \ \ \ $$
之后给出数字n，m，求1-n种与m互质的数的a计算方法之和
做法
通过打表可以发现
$$a_n=n*\left( n+1 \right)$$
所以我们只要能够计算出1-n中所有与m互质的数就可以了，我们发现容斥的某个经典问题就是求1-n中与m互质的数的个数，过程中我们可以算出作为某个组合出的因子的所有倍数的出现次数，我们当时的计算方法是如果这个因子为tmp,那么作为他的倍数的出现次数就是 $time=n/tmp$，那么换到这里，我们想要计算的就是
$$\underset{i=1}{\overset{time}{\varSigma}}\left( i*tmp \right) *\left( i*tmp+1 \right)$$
如果我们设 $t=i*tmp$,上面的式子就变为
$$\underset{i=1}{\overset{time}{\varSigma}}t^2+t$$
$$=\frac{time\times \left( time+1 \right) \times \left( 2\times time+1 \right)}{6}\times t^2+\frac{time\times \left( time+1 \right)}{2}\times t$$
于是这道题就解决了，时间复杂度O(能过)

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int Mod = 1e9+7;
vector<int> v;
ll pow_(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=(ans*a)%Mod;a=(a*a)%Mod;b>>=1;}return ans;
}
ll inv(ll x)
{return pow_(x,Mod-2);
}
ll tmp;
ll cal2(ll x,ll n)
{ll ans=1;ans=(ans*x*x)%Mod;ans=(ans*tmp)%Mod;ans=(ans*n)%Mod;ans=(ans*(n+1))%Mod;ans=(ans*(2*n+1))%Mod;ans=(ans+x*((n*(n+1)%Mod)*inv(2)%Mod)%Mod)%Mod;return ans;
}
ll cal(ll n,ll x)
{ll ans=0;v.clear();for(ll i=2;i*i<=x;i++){if(x%i==0){v.push_back(i);while(x%i==0) x/=i;}}if(x>1) v.push_back(x);int sz=v.size();for(int i=1;i<(1<<sz);i++){int num=0;ll tmp=1;for(int j=0;j<sz;j++){if(i&(1<<j)){num++;tmp*=v[j];}}if(num&1) ans=(ans+cal2(tmp,n/tmp))%Mod;else ans=(ans-cal2(tmp,n/tmp)%Mod+Mod)%Mod;}return (cal2(1,n)-ans%Mod+Mod)%Mod;
}
int main()
{ll n,m;tmp=inv(6);while(scanf("%lld%lld",&n,&m)!=EOF){ll ans=cal(n,m);printf("%lld\n",ans);}return 0;
}