北京软件外包,重庆百度seo整站优化,微信wordpress,包头学做网站文章目录titlesolutioncodetitle
solution
这道题是多么的妙啊#xff0c;完全不是我能推出来的式子呢#xff01; 观察数据范围#xff0c;有点奇怪欸#xff0c;在暗示我#xff1f;#xff1f; 考虑暴力枚举nnn S(n,m)∑i1mφ(ni)S(n,m)\sum_{i1}^mφ(n\times i)S…
文章目录titlesolutioncodetitle
solution
这道题是多么的妙啊完全不是我能推出来的式子呢 观察数据范围有点奇怪欸在暗示我 考虑暴力枚举nnn S(n,m)∑i1mφ(n×i)S(n,m)\sum_{i1}^mφ(n\times i)S(n,m)i1∑mφ(n×i) 神奇的操作来了将nnn质因数分解并把不同的质因数分别拿出一个 n∏piein\prod p_i^{e_i}n∏piei q∏piq\prod p_iq∏pi p∏piei−1p\prod p_i^{e_i-1}p∏piei−1 则有p×qnp\times qnp×qn 若i%j0i\% j0i%j0则φ(ij)φ(i)×jφ(ij)φ(i)\times jφ(ij)φ(i)×j若(i,j)1(i,j)1(i,j)1则φ(ij)φ(i)×φ(j)φ(ij)φ(i)\times φ(j)φ(ij)φ(i)×φ(j) S(n,m)∑i1mφ(n×i)S(n,m)\sum_{i1}^mφ(n\times i)S(n,m)i1∑mφ(n×i)p⋅∑i1mφ(q×i)p\ ·\sum_{i1}^mφ(q\times i)p ⋅i1∑mφ(q×i)p⋅∑i1mφ(qgcd(q,i)×i×gcd(q,i))p\ ·\sum_{i1}^mφ(\frac{q}{gcd(q,i)}\times i\times gcd(q,i))p ⋅i1∑mφ(gcd(q,i)q×i×gcd(q,i))p⋅∑i1mφ(qgcd(q,i))φ(i×gcd(q,i))p\ ·\sum_{i1}^mφ(\frac{q}{gcd(q,i)})φ(i\times gcd(q,i))p ⋅i1∑mφ(gcd(q,i)q)φ(i×gcd(q,i))p⋅∑i1mφ(qgcd(q,i))φ(i)gcd(q,i)p\ ·\sum_{i1}^mφ(\frac{q}{gcd(q,i)})φ(i)gcd(q,i)p ⋅i1∑mφ(gcd(q,i)q)φ(i)gcd(q,i)p∑i1mφ(qgcd(q,i))φ(i)∑d∣gcd(q,i)φ(d)p\sum_{i1}^mφ(\frac{q}{gcd(q,i)})φ(i)\sum_{d|gcd(q,i)}φ(d)pi1∑mφ(gcd(q,i)q)φ(i)d∣gcd(q,i)∑φ(d)p∑i1mφ(i)∑d∣i,d∣qφ(qd)p\sum_{i1}^mφ(i)\sum_{d|i,d|q}φ(\frac{q}{d})pi1∑mφ(i)d∣i,d∣q∑φ(dq)p∑d∣qφ(qd)∑i1⌊md⌋φ(i×d)p\sum_{d|q}φ(\frac{q}{d})\sum_{i1}^{\lfloor\frac{m}{d}\rfloor}φ(i\times d)pd∣q∑φ(dq)i1∑⌊dm⌋φ(i×d)p∑d∣qφ(qd)S(d,⌊md⌋)p\sum_{d|q}φ(\frac{q}{d})S(d,\lfloor\frac{m}{d}\rfloor)pd∣q∑φ(dq)S(d,⌊dm⌋) φφφ用杜教筛应该是老熟人了 S(n,m)S(n,m)S(n,m)记忆化一下应该就没了
code
#include cstdio
#include vector
#include map
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 200000
map int, int mp, s[maxn];
int cnt;
int minp[maxn 5]; //minp[i]:i的最大质因子
int prime[maxn], phi[maxn 5]; //phi[i]:1~i的phi的前缀和
bool vis[maxn 5];void init() {phi[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, minp[i] i, phi[i] i - 1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1, minp[i * prime[j]] prime[j];if( i % prime[j] 0 ) {phi[i * prime[j]] phi[i] * prime[j] % mod;//与式子推导的第二步为什么p能直接从φ里面拿出来呼应break;}elsephi[i * prime[j]] phi[i] * ( prime[j] - 1 ) % mod;}}for( int i 1;i maxn;i ) phi[i] ( phi[i] phi[i - 1] ) % mod;
}int Phi( int n ) {if( n maxn ) return phi[n];if( mp[n] ) return mp[n];int ans n * ( n 1 ) / 2 % mod;for( int i 2, r;i n;i r 1 ) {r n / ( n / i );ans ( ans - ( r - i 1 ) * Phi( n / i ) % mod mod ) % mod;}return mp[n] ans;
}int solve( int n, int m ) {if( ! m ) return 0;if( s[n][m] ) return s[n][m];if( n 1 ) return s[n][m] Phi( m );if( m 1 ) return s[n][m] ( Phi( n ) - Phi( n - 1 ) mod ) % mod;vector int g;int p 1, q 1, N n, x;while( N 1 ) {x minp[N], q * x, N / x, g.push_back( x );while( N % x 0 ) N / x, p * x;}int len g.size(), ans 0;for( int i 0;i ( 1 len );i ) { //枚举q的所有质因子(状压) int d 1;for( int j 0;j len;j )if( i ( 1 j ) ) d d * g[j]; //二进制位为1则有该质因子ans ( ans ( Phi( q / d ) - Phi( q / d - 1 ) mod ) % mod * solve( d, m / d ) % mod ) % mod;}return s[n][m] ans * p % mod;
}signed main() {int n, m;scanf( %lld %lld, n, m );init();int ans 0;for( int i 1;i n;i ) ans ( ans solve( i, m ) ) % mod;printf( %lld\n, ans );return 0;
}
