$\color{blackk}\text{d}\color{red}\text{eco}$ 神!

T1

数位dp不可做,对于50分做法,发现不同 $d(i)$ 上升非常慢,大概只有 $\log$ 级别 利用这个性质可以轻松得到 $50$ 分

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

inline void qread(int &x)
{
x=0; int f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}

inline void qread(long long &x)
{
x=0; long long f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}
}

const int maxn=10000100;

const int modp=998244353;

map <ll,ll> mp;
int dig[maxn],a[maxn],cnt,ans=0;

int getdig(int x)
{
int nowans=1;
while(x)
{
nowans*=x%10;
x/=10;
}
return nowans;
}

int getgcd(int a,int b)
{
if(!b) return a;
return getgcd(b,a%b);
}

int main()
{
// freopen("magic.in","r",stdin);
// freopen("magic.out","w",stdout);
int i,j;
ll n,k;
mstd::qread(n);
mstd::qread(k);
for(i=1;i<=n;i++)
{
dig[i]=getdig(i);
if(!mp[dig[i]]) a[++cnt]=dig[i];
mp[dig[i]]++;
}
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)
{
if(a[i]&&a[j]&&getgcd(max(a[i],a[j]),min(a[i],a[j]))<=k)
ans=(1ll*ans%modp+1ll*mp[a[i]]%modp*mp[a[j]]%modp);
}
printf("%d",ans);
return 0;
}


T2

注意到本质是求一个最小循环节,$\varphi(x+1)\neq x$ 直接排除,此时分母多了个 $\log$ 考虑 $O(n\log n)$ 分解$[1,n]$ 的所有质因子,加上分母的一个 $\log$ ,然后判断 $2^{x}\equiv 1\pmod {(n+1)}$ 即可

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

int ksm(int x,int y,const int modp)
{
int ans=1;
while(y)
{
if(y&1) ans=(1ll*ans*x)%modp;
x=(1ll*x*x)%modp;
y>>=1;
}
return ans;
}

namespace mstd{

inline void qread(int &x)
{
x=0; int f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}

inline void qread(long long &x)
{
x=0; long long f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}
}

const int maxn=(int)1e7+10;

int n,m,p[maxn],cnt,inp[maxn],phi[maxn],pmmn[maxn],looker[maxn];

inline void getprime(int n)
{
phi[1]=1;
inp[1]=1;
int i,j;
looker[1]=1;
for(i=2;i<=n;i++)
{
looker[i]=i;
if(!inp[i]) p[++cnt]=i,phi[i]=i-1,pmmn[i]=cnt;
for(j=1;j<=cnt&&i*p[j]<=n;j++)
{
inp[i*p[j]]=1;
pmmn[i*p[j]]=min(pmmn[i],j);
if(i%p[j]==0)
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}

ll ans=0;
int bj[maxn];

int check(int x)
{
if(inp[x+1]) return 0;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
if(ksm(2,i,(x+1))==1) return 0;
if(ksm(2,x/i,(x+1))==1) return 0;
}
return 1;
}

inline void getans()
{
int i,j;
for(i=1;i<=cnt;i++)
{
for(j=p[i]*2;j<=n;j+=p[i])
{
if(inp[j+1])
{
bj[j]=1;
continue;
}
int usp=1;
while(looker[j]%p[i]==0)
{
looker[j]/=p[i];
usp*=p[i];
bj[j]|=ksm(2,j/usp,j+1)==1;
}
}
}
for(i=1;i<=n;i++) if(looker[i]!=1&&!bj[i]) bj[i]|=ksm(2,i/looker[i],i+1)==1;
for(i=2;i<=n;i+=2) ans+=(bj[i])?0:i;


return ;
}

int main()
{
int i,j;
mstd::qread(n);
getprime((int)1e7+1);
getans();
printf("%.5lf",(double)ans/((double)n/2.0));
return 0;
}


T3

还不会,争取晚上之前打完

总结

T1开场胡到正解然后发现50分都不会,T2没见过这种做法死得好,T3没拿到送的10分很可惜