题解

杨启航，杨坤坤

2026-01-23 16:22:38

发布于：浙江

123阅读

0回复

0点赞

题解
点个赞吧！！！

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=1e6+5,E=2.2*N;
typedef int arr[N];
struct eg{int nx,n,k,w;}e[E];
int n,m,k,M,ce,fi[E],p[2001],q[2001];arr is,pr,mu,Smu,f;
int g(int n,int k){
    if(!n||(n<=M&&k==1))return Smu[n];
    int x=(1LL*n*2017+k)%E;
    for(int i=fi[x];i;i=e[i].nx)if(e[i].n==n&&e[i].k==k)return e[i].w;
    e[++ce]=eg{fi[x],n,k,0};fi[x]=ce;int&w=e[ce].w;
    if(k==1){
        w=1;int i=2,j=sqrt(n),x;
        for(;i<=j;++i)w-=g(n/i,1);
        for(;i<=n;i=j+1)x=n/i,j=n/x,w-=(j-i+1)*g(x,1);
    }else w=g(n,q[k])+g(n/p[k],k);
    return w;
}
int gcd(int a,int b){return!b?a:gcd(b,a%b);}
inline int Sf(int x){return x/k*f[k]+f[x%k];}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    scanf("%d%d%d",&n,&m,&k);
    M=min(N-5,min(n,m));Smu[1]=mu[1]=1;
    fp(i,2,M){
        if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
        for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
            is[x]=1;if(i%pr[j])mu[x]=-mu[i];else break;
        }Smu[i]=Smu[i-1]+mu[i];
    }
    fp(i,1,k)f[i]=f[i-1]+(gcd(i,k)==1);
    fp(i,2,k){
        for(int j=2;;++j)if(i%j==0&&!is[j]){p[i]=j;break;}
        for(q[i]=i;q[i]%p[i]==0;)q[i]/=p[i];
    }
    int i=1,j=sqrt(min(n,m)),x,y,s,t=0;long long w=0;
    for(;i<=j;++i,t=s)s=g(i,k),w+=1ll*(n/i)*Sf(m/i)*(s-t);
    for(;i<=min(n,m);i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),
        s=g(j,k),w+=1ll*x*Sf(y)*(s-t);
    printf("%lld",w);
return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 10

李韵儿（本人必回关）
终于找到一个认识的...

2026-02-10 来自广东
4
不会c++的小女孩 🏆
ok

2026-01-29 来自浙江
4
- 吴羽桐
  回复
  不会c++的小女孩 🏆
  
  2026-04-01 来自广东
  0
坤坤
谢谢

2026-01-23 来自浙江
3
AC桾
1

2026-03-19 来自浙江
2
蒋皓轩

4天前来自浙江
0
༺🆔ljt☯ぬおぎぽゑ☢™༃ༀ
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

using pi = pair<int, int>;
#define mp make_pair
#define f first
#define s second

using vi = vector<int>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define pb push_back
#define bk back()

const int MOD = 1e9 + 7;

template <class T> void remDup(vector<T> &v) {
sort(all(v));
v.erase(unique(all(v)), end(v));
}

struct mi {
int v;
explicit operator int() const { return v; }
mi() : v(0) {}
mi(ll _v) : v(int(_v % MOD)) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
if ((a.v += b.v) >= MOD)
a.v -= MOD;
return a;
}
mi operator+(mi a, mi b) { return a += b; }

const int HASHMAX = 16 * 1000;
struct Table {
mi vals[HASHMAX];
bitset<HASHMAX> visited;
vi keys;
void addTo(int key, mi v) {
if (visited[key] == 0) {
visited[key] = 1;
keys.pb(key);
}
vals[key] += v;
}
void reset() {
for (const auto &u : keys) {
vals[u] = 0;
visited[u] = 0;
}
keys.clear();
}
};

vector<vi> good_subs;
bool is_good_new_set[100005];

void genGoodSubs() {
for (int i = 1; i <= 9; i++) {
good_subs.pb({i});
}
for (int i = 1; i + 3 <= 9; i++) {
good_subs.pb({i, i + 3});
}

for (int i = 1; i <= 2; i++) {
for (int j = 0; j <= 6; j += 3) {
int first_val = i + j;
good_subs.pb({first_val, first_val + 1});
}
}

for (int i = 1; i <= 2; i++) {
for (int j = 0; j <= 3; j += 3) {
vi v;
for (int k = 0; k <= 1; k++) {
for (int l = 0; l <= 3; l += 3) {
v.pb(i + j + k + l);
}
}
sor(v);
good_subs.pb(v);
}
}

for (auto u : good_subs) {
int mask = 0;
for (auto x : u) {
mask += 1 << x;
}
is_good_new_set[mask] = 1;
}
}

void solve() {
string S_inp;
cin >> S_inp;
vi S{-100};
for (auto u : S_inp) {
S.pb(u - '0');
}

int N = sz(S) - 1;

vector<vi> S_masks = vector<vi>(N + 1,

1周前来自浙江
0
136****0371
行

1周前来自福建
0
罐头亏光的EMO小狗（必回关）
谢谢

1周前来自浙江
0
꧁༺ཌༀ༒✨鹿茸✨༒ༀད༻꧂
hi

2026-03-24 来自浙江
0
陈语菡
KEPDOEKDE

2026-03-24 来自浙江
0