o2o网站建设新闻,网站开发需要注册账户吗,广安网站建设,推广软文代发传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
我们设s(x)∑i1nf(x)s(x)\sum_{i1}^nf(x)s(x)∑i1nf(x)#xff0c;那么答案就是s(r)−s(l−1)s(r)-s(l-1)s(r)−s(l−1)。 容易发现#xff0c;我们要求的f(x)f(x)f(x)实际上就是xxx的…传送门
文章目录题意思路题意 思路
我们设s(x)∑i1nf(x)s(x)\sum_{i1}^nf(x)s(x)∑i1nf(x)那么答案就是s(r)−s(l−1)s(r)-s(l-1)s(r)−s(l−1)。 容易发现我们要求的f(x)f(x)f(x)实际上就是xxx的因子的个数那么s(x)∑i1n∑d∣i1s(x)\sum_{i1}^n\sum_{d|i}1s(x)∑i1n∑d∣i1我们改为枚举因子即s(x)∑i1n⌊ni⌋s(x)\sum_{i1}^n\left \lfloor \frac{n}{i} \right \rfloors(x)∑i1n⌊in⌋这个可以整除分块O(n)O(\sqrt n )O(n)求。
// Problem: P3935 Calculating
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3935
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod998244353,INF0x3f3f3f3f;
const double eps1e-6;LL l,r;LL get(LL n) {LL ans0;for(LL l1,r;ln;lr1) {rn/(n/l);ans(r-l1)%mod*((n/l)%mod)%mod; ans%mod;}return ans;
} int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);LL ans0;scanf(%lld%lld,l,r);ansget(r)-get(l-1); ans%mod; ansmod; ans%mod;printf(%lld\n,ans);return 0;
}
/**/
