学习报告1

在上周五的不知道哪里的省赛重现中，遇到了快速等比数列求和取余；

公式推导

 1 int dfs(int x,int b)
 2 {//求出x1+x2+。。。x的b次方的和，并取模tt
 3     if(b==0) return 0;
 4     if(b==1) return x%tt;
 5     int sum=dfs(x,b/2);//求出x1+x2+。。。x的b/2次方的和
 6     int tot=0;
 7     if(b%2==1) //b是奇数
 8         tot=kuaisumi(x,b);
 9     return (sum*(1+qsm(x,b/2))%tt+tot)%tt;
10 }

然后是一题水题

一开始没看数据范围，直接暴力，直接就tle了

#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
bool isprime(int x)
{
    for(int i=2;i<=sqrt(x);i++)
    if(x%i==0) return false;
    return true;
}

bool ishuiwen( int num)
{
    int sum = 0;
    int tmp = num;
    while (num)
    {
        sum = sum * 10 + num % 10;
        num /= 10;
    }
    if (tmp == sum)
        return true;
    return false;

}
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(isprime(i)&&ishuiwen(i))
        cout<<i<<'
';
    }
    return 0;
}

View Code

这里要用到师兄讲的素数筛

bool isprime[n];//1代表是质数，0代表不是
int  prime[n];//素数数组，从小到大装着1到n的素数
void judge()
{
    memset(isprime,true,sizeof(isprime))//默认全都是质数
    int tot=0
    for(int i=2;i<=n;i++)
    {
        if(isprime(i))//是质数
            prime[tot++]=i;//存到素数数组里


        for(int j=0;j<tot&&prime[j]*i<n;j++)
        {
            isprime[ i * prime[j] ]=false;
            if(i%prime[j]==0)//保证每个合数都被它的最小素数筛掉
                break;       
        }
    }
}

直接处理1到一亿的质数，再一个一个判断是不是回文数

AC代码：

#include<iostream>
#include<string.h>
using namespace std;

bool ishuiwen( int num)
{
    int sum = 0;
    int tmp = num;
    while (num)
    {
        sum = sum * 10 + num % 10;
        num /= 10;
    }
    if (tmp == sum)
        return true;
    return false;

}
bool isprime[10000005];
    int prime[10000005];
int main()
{
    
    memset(isprime,true,sizeof(isprime));
    int tot=0;
    for(int i=2;i<=10000005;i++)
    {
        if(isprime[i]==1) prime[tot++]=i;
        for(int j=0;j<tot&&prime[j]*i<10000005;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
            break;
        }
    }
    int a,b;
    cin>>a>>b;
    if(b>10000000) b=10000000;
    for(int i=a;i<=b;i++)
    {
        if(isprime[i]&&ishuiwen(i))
        cout<<i<<'
';
    }
    return 0;
}

View Code