2020 Multi-University Training Contest #1 1010 Math is Simple

2023-12-07 23:08

本文主要是介绍2020 Multi-University Training Contest #1 1010 Math is Simple,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2020 Multi-University Training Contest #1 1010 Math is Simple

题意

hdu-6760 Math is Simple
给定一个n,求解如下式子
在这里插入图片描述

题解

设a+b=n时,设 g ( n ) = ∑ a = 1 n 1 a ( n − a ) [ g c d ( a , n − a ) = = 1 ] [ a < n − a ] g(n)=\sum_{a=1}^n\frac{1}{a(n-a)}[gcd(a,n-a)==1][a<n-a] g(n)=a=1na(na)1[gcd(a,na)==1][a<na], 1 a ( n − a ) = 1 n ( 1 a + 1 n − a ) \frac{1}{a(n-a)}=\frac{1}{n}(\frac{1}{a}+\frac{1}{n-a}) a(na)1=n1(a1+na1)
由对称型可得 g ( n ) = 1 n ( ∑ a = 1 n 1 a [ g c d ( a , n ) = = 1 ] ) g(n)=\frac{1}{n}(\sum_{a=1}^n\frac{1}{a}[gcd(a,n)==1]) g(n)=n1(a=1na1[gcd(a,n)==1])
通过反演再推导出 g ( n ) = 1 n ∑ d ∣ n μ ( d ) 1 d ∑ i = 1 n d 1 i g(n)=\frac{1}{n}\sum_{d|n}\mu(d)\frac{1}{d}\sum_{i=1}^{\frac{n}{d}} \frac{1}{i} g(n)=n1dnμ(d)d1i=1dni1
通过前缀和处理出 ∑ i = 1 n d 1 i \sum_{i=1}^{\frac{n}{d}} \frac{1}{i} i=1dni1
f ( n ) − f ( n − 1 ) = g ( n ) − g ( n − 1 ) f(n)-f(n-1)=g(n)-g(n-1) f(n)f(n1)=g(n)g(n1)
f ( n ) − f ( 2 ) = g ( n ) − g ( 2 ) f(n)-f(2)=g(n)-g(2) f(n)f(2)=g(n)g(2),
f ( n ) = g ( n ) + 1 2 f(n)=g(n)+\frac{1}{2} f(n)=g(n)+21
然后就可以枚举n的因数对 g ( n ) g(n) g(n)进行求解。(卡了预处理 μ ( n ) \mu(n) μ(n)的常数)

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100000000
#define M 11000
#define mod 998244353
#define inv2 499122177
inline int powmod(int a, int b) {int res = 1;a = a % mod;while(b) {if(b & 1) res = (ll)res * a % mod;a = (ll)a * a % mod;b >>= 1;}return res;
}
int inv[N + 5];
void init() {inv[1] = 1;for(int i = 2; i <= N; i++) {inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;}for(int i = 2; i <= N; i++) {inv[i] = (inv[i] + inv[i - 1]) % mod;}
}
int v[50], top;
int res, n;
void dfs(int id, int d, int mu) {if(id == top + 1) {mu = (mu + mod) % mod;res = (res +  (ll)mu * (inv[d] - inv[d - 1] + mod) % mod * inv[n / d] % mod) % mod;return;    }dfs(id + 1, d, mu);dfs(id + 1, d * v[id], -mu);
}
int main() {init();int t;scanf("%d", &t);while(t--) {scanf("%d", &n);if(n == 2) {printf("%d\n", inv2);continue;}int y = n;top = 0;ll invn = powmod(n, mod - 2);for(int i = 2; i * i <= n; i++) {if(n % i == 0) {v[++top] = i;while(n % i == 0) {n /= i;}}}if(n != 1) {v[++top] = n;}n = y;res = 0;dfs(1, 1, 1);res = (1ll * res * invn % mod + inv2) % mod;printf("%lld\n", res);}
}

这篇关于2020 Multi-University Training Contest #1 1010 Math is Simple的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/467658

相关文章

mysqld_multi在Linux服务器上运行多个MySQL实例

《mysqld_multi在Linux服务器上运行多个MySQL实例》在Linux系统上使用mysqld_multi来启动和管理多个MySQL实例是一种常见的做法,这种方式允许你在同一台机器上运行多个... 目录1. 安装mysql2. 配置文件示例配置文件3. 创建数据目录4. 启动和管理实例启动所有实例

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

Post-Training有多重要?一文带你了解全部细节

1. 简介 随着LLM学界和工业界日新月异的发展,不仅预训练所用的算力和数据正在疯狂内卷,后训练(post-training)的对齐和微调方法也在不断更新。InstructGPT、WebGPT等较早发布的模型使用标准RLHF方法,其中的数据管理风格和规模似乎已经过时。近来,Meta、谷歌和英伟达等AI巨头纷纷发布开源模型,附带发布详尽的论文或报告,包括Llama 3.1、Nemotron 340

10400 -Game Show Math

这道题的话利用了暴力深搜,尽管给了20S,但是这样还会超时,所以就需要利用回溯进行减枝,因为是DFS,所以用一个数组vis[i][j]记录是否在状态i时候取到过j值,如果取到过的话,那么直接回溯(往后搜索已经没有意义了,之前到达这个状态的时候是无法得到结果的) 还有需要注意的地方就是题目的要求,每一步的结构都在(-32000,32000)之间,所以需要一步判断,如果在这个范围外直接回溯 最后一

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl