锐客网

  1. 首页 > it技术 > >

HDU 5528 Count a * b

数论

Count a * b 推式子
【HDU 5528 Count a * b】 f ( n ) = ∑ i = 0 n ? 1 ∑ j = 0 n ? 1 n ? i j = n 2 ? ∑ i = 1 n ∑ j = 1 n n ∣ i j = n 2 ? ∑ i = 1 n ∑ j = 1 n n g c d ( i , n ) ∣ i g c d ( i , n ) j = n 2 ? ∑ i = 1 n n n g c d ( i , n ) = n 2 ? ∑ i = 1 n g c d ( i , n ) = n 2 ? ∑ d ∣ n d ∑ i = 1 n ( g c d ( i , n ) = = d ) = n 2 ? ∑ d ∣ n d ∑ i = 1 n d ( g c d ( i , n d ) = = 1 ) = n 2 ? ∑ d ∣ n d ? ( n d ) f(n) = \sum_{i= 0} ^{n - 1} \sum_{j = 0} ^ {n - 1} n \nmid ij\\ = n ^ 2 - \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} n \mid ij\\ = n ^ 2 - \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \frac{n}{gcd(i, n)} \mid \frac{i}{gcd(i, n)}j\\ = n ^ 2 - \sum_{i = 1} ^{n} \frac{n}{\frac{n}{gcd(i, n)}}\\ = n ^ 2 - \sum_{i = 1} ^{n} gcd(i, n)\\ = n ^ 2 - \sum_{d \mid n} d \sum_{i = 1} ^{n} (gcd(i, n) == d)\\ = n ^ 2 - \sum_{d \mid n} d \sum_{i = 1} ^{\frac{n}{d}} (gcd(i, \frac{n}{d}) == 1)\\ = n ^ 2 - \sum_{d \mid n} d \phi(\frac{n}{d})\\ f(n)=i=0∑n?1?j=0∑n?1?n?ij=n2?i=1∑n?j=1∑n?n∣ij=n2?i=1∑n?j=1∑n?gcd(i,n)n?∣gcd(i,n)i?j=n2?i=1∑n?gcd(i,n)n?n?=n2?i=1∑n?gcd(i,n)=n2?d∣n∑?di=1∑n?(gcd(i,n)==d)=n2?d∣n∑?di=1∑dn??(gcd(i,dn?)==1)=n2?d∣n∑?d?(dn?)
g ( n ) = ∑ m ∣ n f ( m ) = ∑ m ∣ n m 2 ? ∑ m ∣ n ∑ d ∣ m d ? ( m d ) = ∑ m ∣ n m 2 ? ∑ d ∣ n d ∑ d ∣ m , m ∣ n ? ( m d ) = ∑ m ∣ n m 2 ? ∑ d ∣ n d ∑ k ∣ n d ? ( k ) = ∑ m ∣ n m 2 ? ∑ d ∣ n n g(n) = \sum_{m \mid n} f(m)\\ = \sum_{m \mid n} m ^ 2 - \sum_{m \mid n} \sum_{d \mid m} d \phi(\frac{m}{d})\\ = \sum_{m \mid n} m ^ 2 - \sum_{d \mid n} d \sum_{d \mid m, m \mid n} \phi(\frac{m}{d})\\ = \sum_{m \mid n} m ^ 2 - \sum_{d \mid n} d \sum_{k \mid \frac{n}{d}} \phi(k)\\ = \sum_{m \mid n} m ^ 2 - \sum_{d \mid n}n\\ g(n)=m∣n∑?f(m)=m∣n∑?m2?m∣n∑?d∣m∑?d?(dm?)=m∣n∑?m2?d∣n∑?dd∣m,m∣n∑??(dm?)=m∣n∑?m2?d∣n∑?dk∣dn?∑??(k)=m∣n∑?m2?d∣n∑?n
有约数个数等于 ∏ i = 1 s u m ( n u m i + 1 ) \prod _{i = 1} ^{sum}(num_i + 1) ∏i=1sum?(numi?+1)
约数之和等于 ∏ i = 1 s u m ( 1 + p i 1 + p i 2 + … … + p i n u m i ) \prod _{i = 1} ^{sum}(1 + p_i ^ {1} + p_i ^{2} + …… + p_i ^{num_i}) ∏i=1sum?(1+pi1?+pi2?+……+pinumi??)
约数平方之和等于 ∏ i = 1 s u m ( 1 + p i 2 + p i 4 + … … + p i 2 n u m i ) \prod _{i = 1} ^{sum}(1 + p_i ^ {2} + p_i ^{4} + …… + p_i ^{2num_i}) ∏i=1sum?(1+pi2?+pi4?+……+pi2numi??)
可以推导，也就是多个等比数列求前n项和，然后累乘。
代码

/* 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 = 1e5 + 10; ull prime[N]; int cnt; bool st[N]; void init() { for(int i = 2; i < N; i++) { if(!st[i]) prime[cnt++] = i; for(int j = 0; j < cnt && i * prime[j] < N; j++) { st[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } }ull quick_pow(ull a, int n) { ull ans = 1; while(n) { if(n & 1) ans = ans * a; a = a * a; n >>= 1; } return 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--) { ull n = read(), m = n; ull ans = 1, sum = 1; for(int i = 0; i < cnt && prime[i] * prime[i] <= n; i++) { if(n % prime[i]) continue; int num = 0; while(n % prime[i] == 0) { n /= prime[i]; num++; } ull res = 1 + prime[i] * prime[i] * ((quick_pow(prime[i], 2 * num) - 1) / (prime[i] * prime[i] - 1)); ans *= res; sum *= 1ull * (num + 1); } if(n != 1) { ans *= 1 + 1ull * n * n; sum *= 2ull; } printf("%llu\n", ans - sum * m); } return 0; }

    推荐阅读


    上一篇：10月23日咖啡冥想

    下一篇：51 NOD 1227 平均最小公倍数（杜教筛）