Strange Function
想到用 $\operatorname{lcm}$ 就可以了。
因为对于 $f(x)=k$ 的 $x$ 的个数就是：
$$\lfloor\dfrac{n}{\operatorname{lcm}(1,2,\cdots,k-1)}\rfloor-\lfloor\dfrac{n}{\operatorname{lcm}(1,2,\cdots,k)}\rfloor$$
然后就没了。。。
很显然 $k$ 不会太大。。。就算拿素数去乘到 41 也早就超过 $10^{16}$。。。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1e2,mo=1e9+7;
ll T,n;
inline ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
inline ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {write(x);putchar(10);}
int main() {
T=read();
while(T--) {
n=read();
ll ans=0,tmp=1;
for(ll i=2;i<=41;i++) {
ans=(ans+n/tmp*i)%mo;
tmp=lcm(tmp,i);
ans=(ans-n/tmp*i+mo)%mo;
}
writeln(ans);
}
return 0;
}
|