Press "Enter" to skip to content

HDOJ6479质数串

题目链接

题面

一个正整数x是质数,当且仅当x≥2且x不是任何一个[2,x−1]的数的倍数。

一个数字串是质数串,当且仅当它的每个非空连续子串表示的数字都是质数。

例子1:”373″是质数串,它的子串有”3″、”37″、”373″、”7″、”73″、”3″,这些串表示的数字都是质数。

例子2:”55″不是质数串,因为”55″这个子串表示的数字不是质数。

相信聪明的你一定已经发现了一个事实,那就是质数串的限制很紧,所以质数串的数量其实非常稀少。

给定一个长度为n的数字串S,请统计它有多少个非空连续子串是质数串。注意两个子串如果位置不同也算不同,比如”373373″中,”373″要算入答案两次。

解题思路

先口算出100以内的所有质数串 2,3,5,7,23,37,53,73

接下来考虑S的长度为3的情况

因为所有以2或者5结尾的数必定是2或者5的倍数,所以后面的那两位只能是3或者7,但是不能是连续的33和77因为这能够被3或者7整除,所以一共有237,273,573,537,373,737这三个数,计算只有373符合条件

接下来考虑S的长度为4的情况

根据规律一共有2373,5373,7373个备选方案,然后全部都不符合条件

因为不存在S长度为4的质数串,所以根据质数串的定义,所以得出不存在长度大于等于4的质数串

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
string d[]={"2","3","5","7","23","37","53","73","373"};
int c(string s,string b)
{
    int cnt=0;
    int n=b.length();
    for (int i = 0; i+n-1 < s.length(); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(s[i+j]!=b[j]){cnt--;break;}
        }
        cnt++;
    }
    return cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T,n;
    string s;
    cin>>T;
    while (T--)
    {
        cin>>n>>s;
        ll ans=0;
        rep(i,0,9)ans+=c(s,d[i]);
        cout<<ans<<endl;
    }

    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x