锐客网

  1. 首页 > it技术 > >

HDU 6706 huntian oy （欧拉函数 + 杜教筛）

杜教筛

huntian oy 推式子
【HDU 6706 huntian oy （欧拉函数 + 杜教筛）】 ∑ i = 1 n ∑ j = 1 i g c d ( i a ? j a , i b ? j b ) ( g c d ( i , j ) = = 1 ) = ∑ i = 1 n ∑ j = 1 i ( i ? j ) ( g c d ( i , j ) = = 1 ) = ∑ i = 1 n i ∑ j = 1 i ( g c d ( i , j ) = = 1 ) ? ∑ i = 1 n ∑ j = 1 i j ( g c d ( i , j ) = = 1 ) = ∑ i = 1 n i ? ( i ) ? ∑ i = 1 n i ? ( i ) + ( i = = 1 ) 2 = ∑ i = 1 n i ? ( i ) ? ( i = = 1 ) 2 然 后 套 路 地 变 成 求 S ( n ) = ∑ i = 1 n i ? ( i ) g ( n ) = n ? ( n ) 这 里 直 接 套 用 杜 教 筛 化 简 得 到 g ( 1 ) S ( n ) = ∑ i = 1 n ( f ? g ) ( i ) ? ∑ i = 2 f ( i ) S ( n i ) ( f ? g ) ( i ) = ∑ d ∣ n f ( d ) ? g ( n d ) = ∑ d ∣ n f ( d ) ? n d ? ( n d ) 另 f ( d ) = d ， 则 有 S ( n ) = ∑ i = 1 n i 2 ? ∑ i = 2 i S ( n i ) 然 后 直 接 套 杜 教 筛 即 可 。 \sum_{i = 1} ^{n} \sum_{j = 1} ^{i}gcd(i ^ a - j ^ a, i ^ b - j ^ b) (gcd(i, j) == 1)\\ = \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} (i - j)(gcd(i, j) == 1) \\ = \sum_{i = 1} ^{n} i\sum_{j = 1} ^{i} (gcd(i, j) == 1) - \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} j (gcd(i, j) == 1)\\ = \sum_{i = 1} ^{n} i \phi(i) - \sum_{i = 1} ^{n} \frac{i \phi(i) + (i == 1)}{2}\\ = \sum_{i = 1} ^{n} \frac{i \phi(i) - (i == 1)}{2}\\ 然后套路地变成求S(n) = \sum_{i = 1} ^{n} i \phi(i)\\ \\g(n) = n \phi(n)\\ 这里直接套用杜教筛化简得到g(1)S(n) = \sum_{i = 1} ^{n} (f*g)(i) - \sum_{i = 2} f(i)S(\frac{n}{i})\\ (f * g)(i) = \sum_{d \mid n} f(d) *g(\frac{n}{d}) = \sum_{d \mid n} f(d) * \frac{n}{d} \phi(\frac{n}{d})\\ 另f(d) =d，则有S(n) = \sum_{i = 1} ^{n} i ^ 2 - \sum_{i = 2} i S(\frac{n}{i})\\ 然后直接套杜教筛即可。 i=1∑n?j=1∑i?gcd(ia?ja,ib?jb)(gcd(i,j)==1)=i=1∑n?j=1∑i?(i?j)(gcd(i,j)==1)=i=1∑n?ij=1∑i?(gcd(i,j)==1)?i=1∑n?j=1∑i?j(gcd(i,j)==1)=i=1∑n?i?(i)?i=1∑n?2i?(i)+(i==1)?=i=1∑n?2i?(i)?(i==1)?然后套路地变成求S(n)=i=1∑n?i?(i)g(n)=n?(n)这里直接套用杜教筛化简得到g(1)S(n)=i=1∑n?(f?g)(i)?i=2∑?f(i)S(in?)(f?g)(i)=d∣n∑?f(d)?g(dn?)=d∣n∑?f(d)?dn??(dn?)另f(d)=d，则有S(n)=i=1∑n?i2?i=2∑?iS(in?)然后直接套杜教筛即可。
代码

/* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include #define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f; inline ll read() { ll f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-')f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f * x; }const int N = 1e6 + 10, mod = 1e9 + 7, inv2 = 500000004, inv6 = 166666668; int prime[N], cnt; ll phi[N]; bool st[N]; ll quick_pow(ll a, ll n) { ll ans = 1; while(n) { if(n & 1) ans = ans * a % mod; n >>= 1; a = a * a % mod; } return ans; }void init() { phi[1] = 1; for(int i = 2; i < N; i++) { if(!st[i]) { prime[cnt++] = i; phi[i] = i - 1; } for(int j = 0; j < cnt && i * prime[j] < N; j++) { st[i * prime[j]] = 1; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } for(int i = 1; i < N; i++) { phi[i] = (1ll * phi[i] * i + phi[i - 1]) % mod; } }ll calc(int n) { return 1ll * n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod; }unordered_map ans_s; ll S(int n) { if(n < N) return phi[n]; if(ans_s.count(n)) return ans_s[n]; ll ans = calc(n); for(int l = 2, r; l <= n; l = r + 1) { r = n / (n / l); ans = (ans - 1ll * (r + l) * (r - l + 1) / 2 % mod * S(n / l) % mod + mod) % mod; } return ans_s[n] = ans; }int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); init(); int T = read(); while(T--) { int n = read(), a = read(), b = read(); printf("%lld\n", (S(n) - 1 + mod) % mod * inv2 % mod); } return 0; }

    推荐阅读


    上一篇：除了“对你好”还必须有别的值得你嫁的才行

    下一篇：微商怎么找产品（通过五点学习重要的微商技巧）