用啥筛

mzm_0808 @ 2024-08-30 22:30:52

by eatkeyboard @ 2024-08-30 22:32:29

线性筛又称欧拉筛

by meifan666 @ 2024-08-30 22:32:32

@u13857022545 都能AC

by hyl_____ @ 2024-08-30 22:36:10

@meifan666 借楼向大佬求条

#include<bits/stdc++.h>
using namespace std;    
char c1[10000010],c2[10000010];
int main()
{

    long long n1,n2;
    while(!(scanf("%s %d %s %d",&c1,&n1,&c2,&n2)!=4))
    {
        long long len1=strlen(c1);
        long long len2=strlen(c2);
//      cout<<len1<<" "<<len2<<endl;
        for(int i=1;i<=n1;i++) 
        {
            for(int sum=0;sum<len1;sum++)
            {
                c1[sum+len1*i]=c1[sum];
            }
        }
        for(int i=1;i<=n2;i++) 
        {
            for(int sum=0;sum<len2;sum++)
            {
                c2[sum+len2*i]=c2[sum];
            }
        }
        len1=len1*n1;
        len2=len2*n2;
        if(len1==len2) cout<<1;
        else if(len1<len2) cout<<0;
        else
        {
            int ans=0;
            int sum=0;
            for(int i=0;i<len2;i++)
            {
                if(c1[sum]==c2[i]) sum++;
                else sum=0;
                if(sum==len1) ans++,sum=0;
            }
            cout<<ans<<endl;
        }
    } 
    return 0;
}

P10976 RE

by meifan666 @ 2024-08-30 22:37:54

@hyl_____ 完了，尴尬了，我是蒟蒻，这题没做过

by hyl_____ @ 2024-08-30 22:39:45

@meifan666 没事，看代码那里RE就行

by meifan666 @ 2024-08-30 22:43:36

@hyl_____

c1[sum+len1*i]=c1[sum];

这句会到 1e8，数组差一点

by hyl_____ @ 2024-08-30 22:45:01

@meifan666 感谢大佬

by leozhao123 @ 2024-08-30 22:45:47

@meifan666 膜拜隔壁

by meifan666 @ 2024-08-30 22:47:18

@leozhao123 赵bw?

by hyl_____ @ 2024-08-30 22:50:12

@meifan666 再……求条 TLE

#include<bits/stdc++.h>
using namespace std;    
char c1[100000010],c2[100000010];
int main()
{

    long long n1,n2;
    while(!(scanf("%s %d %s %d",c1,&n1,&c2,&n2)!=4))
    {
        int len1=strlen(c1);
        int len2=strlen(c2);
        for(int i=1;i<=n1;i++) 
        {
            for(int sum=0;sum<len1;sum++)
            {
                c1[sum+len1*i]=c1[sum];
            }
        }
        for(int i=1;i<=n2;i++) 
        {
            for(int sum1=0;sum1<len2;sum1++)
            {
                c2[sum1+len2*i]=c2[sum1];
            }
        }
        len1=len1*n1;
        len2=len2*n2;
//      cout<<len1<<" "<<len2<<endl;
        if(len1==len2) cout<<1;
        else if(len1>len2) cout<<0;
        else
        {
            int ans=0;
            int sum=0;
            for(int i=0;i<len2;i++)
            {
                if(c1[sum]==c2[i]) sum++;
                else sum=0;
                if(sum==len1) ans++,sum=0;
            }
            cout<<ans<<endl;
        }
    } 
    return 0;
}