欧拉之路

Multiples of 3 and 5

求1000以内3的倍数或者5的倍数的和

考虑容斥，分别加上$3$和$5$的倍数，然后减去$lcm(3,5)$也就是$15$的倍数

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int s(int x){
    return x*(x+1)/2;
}
int main(){
    int a=3,b=5,n=999;
    int g=a*b/gcd(a,b);
    printf("%d
",a*s(n/a)+b*s(n/b)-g*s(n/g));
}

Even Fibonacci numbers

求斐波拉契每一项是偶数值的和

$O(N)$直接DP即可用递推公式$f[n]=f[n-1]+f[n-2]$

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int dp[N];
long long ans=2;
int main(){
    int n=4000000;
    dp[1]=1,dp[2]=2;
    for(int i=3;;i++){
        dp[i]=dp[i-1]+dp[i-2];
        if(dp[i]>n)break;
        if(dp[i]%2)ans+=dp[i];
    }
    cout<<ans;
    return 0;
}

Largest prime factor

找一个数最大的质因子

$O(sqrt n)$暴力找素数即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int get_max_prime(int x){
    int ans=-1;
    for(int i=2;i<=x&&x!=1;i++)
        while(x%i==0)x/=i,ans=max(ans,i);
    if(x!=1)ans=max(ans,x);
    return ans;
}
signed main(){
    int n=600851475143;
    printf("%lld
",get_max_prime(n));
}

Largest palindrome product

查找两个数相乘是回文数的最大的回文数

暴力$O(n^2)$比较，判断是否回文，稍微剪剪枝，T到飞起

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long ans=0;
int check(int x){
    stringstream ss;
    string s;
    ss<<x;
    ss>>s;
    int len=s.size()-1;
    for(int i=0;i<=len-i;i++)
        if(s[i]!=s[len-i])return false;
    return true;
}
int main(){
    for(int i=999;i>=100;i--){
        for(int j=999;j>=100;j--){
            if(i*j<=ans)break;
            ans=max(ans,1ll*check(i*j)*i*j);
        }
    }
    cout<<ans;
    return 0;
}

Smallest multiple

查找能被1-n整除的最小的数

找$lcm(a_1,a_2...a_n)$然后输出即可考虑$O(n)$处理

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=20;
    long long ans=1;
    for(int i=1;i<=n;i++)
    {
        ans/=__gcd(ans,1ll*i);
        ans*=i;
    }
    cout<<ans<<endl;
    return 0;
}

Sum square difference

找平方和 和 和平方的差

$O(n)$依照题意模拟暴力即可

#include<bits/stdc++.h>
using namespace std;
long long ans;
int main(){
    for(int i=1;i<=100;i++){
        ans+=i*i;
    }
    cout<<5050*5050-ans;
    return 0;
}

10001st prime

找第10001个质数
考虑欧拉线性筛，当质数个数等于10001的时候输出即可

#include<bits/stdc++.h>
using namespace std;
int pr[1000010],st[1000010],cnt;
int get(int n,int k)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])st[i]=1,pr[++cnt]=i;
        if(cnt==k)return pr[k];
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main()
{
    printf("%d
",get(1000000,10001));
    return 0;
}

Largest product in a series

给你许多数，找出连续13个乘积最大

考虑暴力模拟取最大值即可，也可以使用队列，并记录其中为0的个数（因为直接除以0会RE）$O(n)$模拟

#include<bits/stdc++.h>
using namespace std;
long long answer;
string s="07316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
int main(){
    for(int i=1;i+12<=1000;i++){
        long long ans=1;
        for(int j=0;j<13;j++)
            ans*=(s[i+j]-'0');
        answer=max(answer,ans);
    }
    cout<<answer;
    return 0;
}

Special Pythagorean triplet

求egin{cases} a^2+b^2=c^2 \ a+b+c=1000 end{cases} 的唯一解

考虑枚举a,b并通过第二个求出c，再判断是否合法

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=1000,ans=-1;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n&&i+j<1000;j++)
        {
            int k=1000-i-j;
            if(i*i+j*j==k*k)ans=max(ans,i*j*k);
        }
    printf("%d
",ans);
    return 0;
}

Summation of primes

求2000000以下的素数和

考虑$O(n)$欧拉筛出2000000以下的素数然后相加

#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
long long ans,len;
int v[N],p[N];
void prime(int n){
    for(int i=2;i<=n;i++){
        if(!v[i]){
            v[i]=1;
            p[++len]=i;
            ans+=i;
        }
        for(int j=1;j<=len&&i*p[j]<=n;j++){
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    cout<<ans;
}
int main(){
    prime(2000000);
    return 0;
}

Largest product in a grid

给你一个矩阵，求出连续四个数（可以横竖对角线）使得乘积最大

$O(nm)$，每个点只需要向下，右下，右，右上扩展即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[110][110];
signed main()
{
    int n=20,ans=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lld",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int a1=a[i][j]*a[i+1][j]*a[i+2][j]*a[i+3][j];
            int a2=a[i][j]*a[i][j+1]*a[i][j+2]*a[i][j+3];
            int a3=a[i][j]*a[i+1][j+1]*a[i+2][j+2]*a[i+3][j+3];
            int a4=a[i][j]*a[i-1][j+1]*a[i-2][j+2]*a[i-3][j+3];
            ans=max(ans,max(a1,max(a2,max(a3,a4))));
        }
    printf("%lld
",ans);
    return 0;
}

Highly divisible triangular number

求从小到大第一个i使得$d({sum_{j=1}^i j})>500$

考虑暴力枚举然后$sqrt n$查找即可

#include<bits/stdc++.h>
using namespace std;
const int N=70100000;
int check(int n){
    int ans=0;
    for(int i=1;i*i<n;i++){
        if(n%i==0)ans+=2;
    }
    if((int)sqrt(n)*(int)sqrt(n)==n)ans++;
    return ans;
}
int main(){
    long long sum=0;
    for(int i=1;;i++){
        sum+=i;
        if(check(sum)>500){
            cout<<sum<<endl;
            return 0;
        }
    }
    return 0;
}

Large sum

高精度加法，然后求前十位

高精度搞一搞

#include<bits/stdc++.h>
using namespace std;
string a[110];
int d[510];
int main(){
    int n=100,m=50,k=10;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        reverse(a[i].begin(),a[i].end());
    }
    for(int j=0;j<m;j++)
        for(int i=1;i<=n;i++)
            d[j]+=(a[i][j]-'0');
    for(int j=0;j<m*2;j++)
        d[j+1]+=d[j]/10,d[j]%=10;
    int st;
    for(st=m*2;st&&!d[st];st--);
    for(int j=st;j>st-k;j--)
        printf("%d",d[j]);
    return 0;
}

Longest Collatz sequence

给你一个$f(n)=$ egin{cases} n/2, & mbox{if }nmbox{ is even} \ 3n+1, & mbox{if }nmbox{ is odd} end{cases}
然后求最长能操作的次数

考虑记忆化，但是空间可能开不下，所以指定一个小范围，范围内记忆化即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10000010;
int dp[N];
int ans,answer;
int check(int n){
    if(n==1)return 1;
    if(n%2==0)
        return check(n/2)+1;
    return check(3*n+1)+1;
}
signed main(){
    for(int i=1;i<=1000000;i++){
        int PPP=check(i);
        if(PPP>ans){
            ans=PPP;
            answer=i;
        }
    }
    cout<<answer;
    return 0;
}

Lattice paths

给你一个n*n方格求出从左上角到右下角的方案数

方案一：可以考虑$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
方案二：总共可以向下走$n$次，向右走$n$次，所以可以转换成一个组合数问题，也就是从$2n$里面选择$n$个，$C_{2n}^n$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int C(int n){
    int fac=1;
    for(int i=n+1;i<=2*n;i++)
        (fac*=i)/=(i-n);
    return fac;
}
signed main(){
    int n=20;
    printf("%lld
",C(20));
    return 0;
}

Power digit sum

高精度乘法

暴力模拟搞一搞

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
long long ans;
int main(){
    a[1]=1;
    int n=1000;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=20000;j++){
            a[j]*=2;
        }
        for(int j=1;j<=20000;j++){
            a[j+1]+=a[j]/10;
            a[j]%=10;
        }
    }
    for(int i=1;i<=20000;i++)
        ans+=a[i];
    cout<<ans;
    return 0;
}

Number letter counts

求出1-1000用英文表示需要多少个字符

怪恶心的

模拟每一个数转换成英文要多少个字符即可

#include<bits/stdc++.h>
int ud100[20]={0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8};
int ov100[10]={0,0,6,6,5,5,5,7,6,6};
int len(int x){
    if(x<20)return ud100[x];
    else if(x<100)return ud100[x%10]+ov100[x/10];
    else if(x<1000){
        if(x%100==0)return ud100[x/100]+7;
        else return ud100[x/100]+len(x%100)+10;

    }
    else return 11;
}

int main(){
    int sum=0;
    for(int i=1;i<=1000;i++)
        sum+=len(i);
    printf("%d
",sum);
    return 0;
}

Maximum path sum I

数字三角形

$dp[i][j]$表示第i行第j列能得到的最大价值

考虑$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]$即可

#include<bits/stdc++.h>
using namespace std;
int ans;
int a[110][110];
int main(){
    int n=15;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
            a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
            ans=max(ans,a[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

Counting Sundays

数星期日在一个月的第一天有多少个

首先题目给的是1900年1月1日的，我们先算出1901年1月1日是星期二，然后判断每一个月多少天模拟即可

#include<bits/stdc++.h>
using namespace std;
int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
    int sum=0,now=1,y,m,d;
    int Y=2000; 
    for(y=1901;y<=2000;y++)
        for(m=1;m<=12;m++)
            for(d=1;d<=day[m]+(m==2)*((y%4==0)-(y%100==0)+(y%400==0));d++)
            {
                now++;
                if(now==7)
                {
                    now=0;
                    if(d==1)sum++;
                }
            }
    printf("%d
",sum);
    return 0;
}

Factorial digit sum

阶乘求各位之和

高精度搞一搞

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
long long ans;
int main(){
    1[a]=1;
    for(int i=1;i<=100;i++){
        for(int j=1;j<=20000;j++){
            j[a]*=i;
        }
        for(int j=1;j<=20000;j++){
            (j+1)[a]+=j[a]/10;
            j[a]%=10;
        }
    }
    for(int i=1;i<=20000;i++)
        ans+=i[a];
    cout<<ans;
    return 0;
}

Amicable numbers

记d(i)为i的真因数和
定义两个数a,b

$if(d(a)=b && d(b)=a)$
那么这两个数都是亲和数，这一对数称为亲和数对
求出10000以内的亲和数之和

考虑欧拉筛出$d(i)$然后减去自己得到每个输得真因数和，然后$O(n)$找出亲和数相加即可

#include<bits/stdc++.h>
using namespace std;
const int N=10100;
int f[N],g[N],p[N],used[N];
int len;
long long ans;
inline void get_f(int n){
    f[1]=g[1]=1;
    for(int i=2;i<=n;i++){
        if(!used[i]){
            used[i]=1;
            p[++len]=i;
            g[i]=f[i]=i+1;
        }
        for(int j=1;j<=len&&i*p[j]<=n;j++){
            used[p[j]*i]=1;
            if(i%p[j]==0){
                g[i*p[j]]=g[i]*p[j]+1;
                f[i*p[j]]=f[i]/g[i]*g[i*p[j]];
                break;
            }
            else{
                f[i*p[j]]=f[i]*f[p[j]];
                g[i*p[j]]=1+p[j];
            }
        }
    }
    for(int i=1;i<=n;i++)
        f[i]-=i;
}
int main(){
    get_f(10000);
    for(int i=1;i<10000;i++){
        if(f[f[i]]==i&&i!=f[i])ans+=i;
    }
    cout<<ans;
    return 0;
}

Names scores

给你许多名字，求出名字序号*每个字母的排名，累加

先处理恶心的格式，然后排序，然后计算每个数的分值，相加即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string a[100010];
inline ll idx(string x){
    ll fac=0;
    for(int i=0;i<x.size();i++)
        fac+=(x[i]-'A'+1);
    return fac;
}
int main(){
    int n=0;
    ll ans=0;
    while(cin>>a[++n]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
//        if(a[i]=="COLIN")printf("%lld
",1ll*(i-1)*idx(a[i]));
        ans+=1ll*(i-1)*idx(a[i]);
    }
    printf("%lld
",ans);
    return 0;
}

Non-abundant sums

定义一个数$n$，$d(n)$为$n$的真因数之和

$if(d(n)=n)$称为完全数
$if(d(n)>n)$称为盈数
$if(d(n)<n)$称为亏数
已知大于28123都能表示为两个盈数相加
求出不能表示为两个盈数相加的数的总和

考虑$O(n)$筛出$d(i)$然后再计算出盈数push进一个vector，再双重for循环打标机，最后累计一遍没有打上标记的即可

#include<bits/stdc++.h>
using namespace std;
const int N=30000;
int len,ans;
int g[N],f[N],v[N],p[N];
vector<int>res;
void get_f(int n){
    g[1]=f[1]=1;
    for(int i=2;i<=n;i++){
        if(!v[i]){
            v[i]=1,
            p[++len]=i;
            g[i]=f[i]=i+1;
        }
        for(int j=1;j<=len&&p[j]*i<=n;j++){
            v[p[j]*i]=1;
            if(i%p[j]==0){
                g[i*p[j]]=g[i]*p[j]+1;
                f[i*p[j]]=f[i]/g[i]*g[i*p[j]];
            }
            else{
                g[i*p[j]]=p[j]+1;
                f[i*p[j]]=f[i]*f[p[j]];
            }
        }
    }
    for(int i=1;i<=n;i++)
        f[i]-=i;
}
int main()
{
    get_f(28123);

    for(int i=1;i<=28123;i++){
        if(f[i]>i)res.push_back(i);
    }
    memset(v,0,sizeof v);
    for(int i=0;i<res.size();i++){
        for(int j=i;j<res.size();j++){
            v[res[i]+res[j]]=1;
        }
    }
    for(int i=1;i<=28123;i++){
        if(!v[i])ans+=i;
    }
    cout<<ans;
    return 0;
}

Lexicographic permutations

给你一个n=10的（0到9）序列，求出排名第1000000的序列是多少

考虑搜索或者next_permutation()O(k)求出排列
但还有一种更高级的方法——逆康托展开
具体原理链接已挂，不做解释
能$O(n log n)$算出排列，但是一般由于阶乘问题，n不会很大

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int k=1000000,n=10;
ll fac[11];
vector<int>s;
int main(){
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i,s.push_back(i);
    k--;
    for(int i=9;i>=0;i--){
        int p=k/fac[i];
        printf("%d ",s[p]-1);
        s.erase(lower_bound(s.begin(),s.end(),s[p]));
        k%=fac[i];
    }

}

1000-digit Fibonacci number

求出第几项斐波拉契位数大于等于1000

高精度模拟

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a[110010];
    int len;
    node(){
        memset(a,0,sizeof a);
        len=0;
    }
    node operator+(const node &x)const{
        node c;
        for(register int i=1;i<=1000;i++)
            c.a[i]=a[i]+x.a[i];
        for(register int i=1;i<=1000;i++){
            c.a[i+1]+=c.a[i]/10;
            c.a[i]%=10;
            if(c.a[i])c.len=max(c.len,i);
        }
        return c;
    }
}f[4];
int main(){

    f[1].a[1]=1;
    f[2].a[1]=1;
    for(int i=3;;i++){
        f[(i+1)%3]=f[i%3]+f[(i+2)%3];
        if(f[(i+1)%3].len>=1000){
            cout<<i;
            return 0;
        }
    }

}

Reciprocal cycles

求出1000以内对于每一个$i$,$frac{1}{i}$循环节位数最大的一个i并输出

循环节可能很大，所以我们模拟人工运算，去拿余数*10继续试除，考虑拿余数记录这一位是否重复（如果余数相同，那么后面的肯定也还是相同的），所以只需要打标记，如果访问到了就拿这一次的减去上次访问的就是循环节的长度了

#include<bits/stdc++.h>
using namespace std;
int f[100001];
int first[100001];
int pre[1001];
bool flag;
int ans,answer;
void work(int k,int x,int i){
    if(flag)return;
    k*=10;
    k%=x;
    if(pre[k]){
        f[x]=i-pre[k];
        flag=1;
        return;
    }
    pre[k]=i;
    work(k,x,i+1);
}
int main(){
    for(int i=1;i<=1000;i++){
        flag=0;
        memset(pre,0,sizeof pre);
        work(1,i,1);
        if(f[i]>ans){
            ans=f[i];
            answer=i;
        }
    }
    cout<<ans<<" "<<answer<<endl;
    return 0;
}

Quadratic primes

给你$n^2+an+b$其中$(|a|<1000,|b|leq 1000)$
求出一对$a,b$使得$n$从0开始，连续答案的都是素数的最长连续个数

考虑先晒出素数打标记然后暴力模拟

#include<bits/stdc++.h>
using namespace std;
const int N=10000000;
int len,ans,answer;
int p[1000010];
int v[N+1];
void get(){
    for(int i=2;i<=N;i++){
        if(!v[i]){
            v[i]=2;
            p[++len]=i;
        }
        for(int j=1;j<=len&&i*p[j]<=N;j++){
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
int main(){
    get();
    for(int a=-1000;a<=1000;a++){
        for(int b=-1000;b<=1000;b++){
            for(int l=0;;l++){
                if(l*l+a*l+b<0||v[l*l+a*l+b]!=2)break;
                if(l+1>ans)ans=l+1,answer=a*b;
                ans=max(ans,l+1);
//                printf("%d ",ans);
            }
        }
    }
    cout<<answer;

    return 0;
}

Number spiral diagonals

类似于螺旋矩阵那种，给你边长求对角线之和

这种是奇偶分开考虑，这里只有奇数的，找个规律发现下一个增加的是2,2,2,2,4,4,4,4,6,6,6,6...然后循环即可

#include<bits/stdc++.h>
using namespace std;给你
long long ans,pre=1;
int main(){
    int n=1001;
    for(int i=2;i<=n;i+=2){
        for(int j=1;j<=4;j++){
            pre=pre+i;
            ans+=pre;
        }
    }
    cout<<ans+1;
    return 0;
}

Distinct powers

给你一个$a*b$的方阵，其中$v[i][j]=i^j$问你去重后总共有多少个元素

首先你可以考虑高精度这精度要上天了但是我很懒
我们想，对于一个数$k$，他可能会和$k^2,k^3,k^4...k^x$重合，所以我们只需要考虑枚举最简的k即可

然后记录他能到达多少次幂，ans加一加，时间复杂度是$O(nm)$

然后思考n,m更大时候的做法

对于$2,2^2,2^3,2^4$他能取得种类一定和$3,3^2,3^3,3^4$是一样的

所以我们考虑先$O(nlogm)$求出所有的种类数(因为最多要考虑的只有$log m$个也就是2次幂)，然后$O(n)$走一遍，打个标记就行了

整体时间复杂度$O(nlogm)$

$O(n^2)$

#include<bits/stdc++.h> 
#define n 101
#define m 6001
using namespace std;
bool used[n];
bool flag[m];
int ans=0,t;
int main(void)
{
    for(int i=2,j;i<n;i++){
        if(!used[i]){
            t=i;
            memset(flag,0,sizeof flag);
            for(j=2;j<n;j++){
                t=t*i;
                if(t>=n)break;
                used[t]=true;
            }
            for(int k=1;k<j;k++)
                for(int l=2;l<n;l++)
                    flag[k*l]=true;
            for(int k=2;k<m;k++){
                if(flag[k]){
                    ans++;
                }
            }
        }

    }
    printf("%d
",ans);
    return 0;
}

 $O(n log m)$

#include<bits/stdc++.h> 
#define n 1001
#define m 600001
using namespace std;
bool used[n];
bool flag[m];
int check[m];
int ans=0,t,res;
int main(void)
{
    //    ans=(n-2)*(n-2);
    for(int k=1;k<log2(n);k++){//提前预处理 
        for(int l=2;l<n;l++){
            if(!flag[k*l])
                flag[k*l]=true,res++;
        }
        check[k]=res;
    }
    for(int i=2,j;i<n;i++){//因为有标记，所以是O(n)的复杂度 
        if(!used[i]){
            t=i;
            memset(flag,0,sizeof flag);
            for(j=2;j<n;j++){
                t=t*i;
                if(t>=n)break;
                used[t]=true;
            }
            ans+=check[j-1];
        }

    }
    printf("%d
",ans);
    return 0;
}

Digit fifth powers

让你找出所有的各位数字5次幂之和加起来等于本身的数，并输出他们的和

考虑暴力计算每一位的和，但是这里的上限是未知的，所以需要有一个判断

如果i位数，每一位都是9加起来还没这个数大，那后面的基本都不可能了，返回就可以了

#include<bits/stdc++.h>
using namespace std;
int n=5;
string s;
long long ans,res;
long long fac[10];
int main(){
    for(int i=1;i<=9;i++)
        fac[i]=pow(i,n);
    for(int i=2;i;i++){
        res=0;
        stringstream ss;
        ss<<i;
        ss>>s;
        for(int j=0;j<s.size();j++)
        {
            res+=fac[s[j]-'0'];
            if(res>i)break;
        }
        if(res==i)ans+=i;
        if(fac[9]*s.size()<i)break;
    }
    cout<<ans;
    return 0;
}