51nod 1040 最大公约数之和

Type:欧拉函数,gcd性质,思维

题目

给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15

题解

N<=10^9,所以肯定无法暴力枚举
考虑我们要求 lambda(gcd(i,N) | i∈[1,N])

我们可以知道:
对于每个数N,他的约数范围在[1~N]之间,即我们可以将问题转化为(设约数为Ni,1~N中约数为Ni个数为Mi):

lambda(Ni*Mi)

假设我们已经得到了Ni,问题就在于我们如何求出Mi
设i为1~N中任意数:

(1) Mi=count(gcd(i,N)=Ni | i∈[1~N])
=count(gcd(i/Ni,N/Ni)=1 | i∈[1~N])

即我们只需要求出1~N中与N/Ni互素的数的个数即可

即 euler(N/Ni)

(2) Mi=euler(N/Ni)

ans=lambda(Ni*euler(N/Ni))

然后有一个小性质,即 i*i<=N时,我们枚举到sqrt(i)同时求出 N/i ,枚举完所有的 i 即枚举完所有 1~N 内 N 的约数.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N;

LL euler(LL n){
    LL res=n,a=n;
    for(LL i=2;i*i<=a;++i){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0)a/=i;
        }
    }
    if(a>1)res=res/a*(a-1);
    return res;
}

int main(){
    while(~scanf("%lld",&N)){
        LL ans=0;
        for(LL i=1;i*i<=N;++i){
            if(N%i==0){
                ans+=(i*euler(N/i));
                if(i*i!=N){
                    ans+=((N/i)*euler(i));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

山东省第七届省赛

A:水

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,A,B;
    while(~scanf("%d",&T)){
        for(int i=0;i<T;++i){
            cin>>A>>B;
            if(A%B){
                cout<<(A/B)+1<<endl;
            }else{
                cout<<(A/B)<<endl;
            }
        }
    }
    return 0;
}

B:二分(或者可以暴力,只有45个FB)结论题,用到斐波那契博弈里的一个结论:任何数都可以被拆成不同斐波那契的和,进而猜测直接从最大的小于N的FB往下找即可

我吐槽下SDUT的OJ…尼玛10^9能写成109,劳资找了大大大大大大半天错硬是不知道错哪里了艹

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int Fb[maxn],M;
int vis[maxn],has_ans;

void init(){
    Fb[0]=1;
    Fb[1]=2;
    for(int i=2;i<maxn;++i){
        Fb[i]=Fb[i-1]+Fb[i-2];
        //printf("%d\n",Fb[i]);
    }

}

void solve(int N){
    stack<int> ans;
    int mx=maxn;
    while(N!=0){
        int ind=lower_bound(Fb,Fb+mx,N)-Fb;
        if(Fb[ind]>N)ind-=1;
        N=N-Fb[ind];
        ans.push(Fb[ind]);
    }
    printf("%d=",M);
    int t=0;
    while(!ans.empty()){
        if(!t){
            printf("%d",ans.top());t++;
        }else printf("+%d",ans.top());
        ans.pop();
    }
    printf("\n");
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        has_ans=0;
        scanf("%d",&M);
        solve(M);
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 40ms
Take Memory: 196KB
Submit time: 2018-03-04 13:39:50
****************************************************/

E:简单枚举

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;

int T,N,M;
char mp[maxn][maxn];
int dist[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

bool check(int x,int y){
    if(x<1 || x>M || y<1 || y>N) return false;
    return true;
}

int main(){
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d%d",&M,&N);
        for(int i=1;i<=M;++i){
            scanf("%s",mp[i]+1);
        }
        for(int i=1;i<=M;++i){
            for(int j=1;j<=N;++j){
                if(mp[i][j]=='#'){
                    for(int k=0;k<4;++k){
                        int x=i+dist[k][0],y=j+dist[k][1];
                        if(check(x,y)){
                            if(mp[x][y]=='#')continue;
                            int room=0;
                            for(int kk=0;kk<4;++kk){
                                int xx=x+dist[kk][0],yy=y+dist[kk][1];
                                if(check(xx,yy)){
                                    if(mp[xx][yy]=='#')++room;
                                }
                            }
                            if(room==1)ans++;
                        }else ++ans;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 228ms
Take Memory: 212KB
Submit time: 2018-03-04 14:46:06
****************************************************/

G:找规律,不像博弈,抱歉,会打表,但是规律想不出来,对不起

打表

#include<bits/stdc++.h>
using namespace std;

int solve(int N){
    int ans=0;
    for(int i=1;i<N;++i){
        for(int j=i;j<N-i;++j){
            int k=N-i-j;
            if((i^j^k)==0) ans++;
        }
    }
    return ans;
}

int main(){
    for(int i=1;i<=200;++i){
        printf("%d: %d\n",i,solve(i)/3);
    }
    return 0;
}

找的规律,知道规律了,直接粘的别人代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans,pp;
    int i;
    long long int f[100];
    f[2]=1;
    f[1]=0;
    f[0]=0;
    for(i=3;i<30;i++)
        f[i]=f[i-1]*3+1;
    long long int a;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a;
        ans=0;
        if(a%2)
        {
            cout<<0<<endl;
            continue;
        }
        while(a!=0)
        {
            pp=a%2;
            if(pp)
                ans++;
            a/=2;
        }
        cout<<f[ans]<<endl;
    }
}

J:题目翻译: http://www.bubuko.com/infodetail-1612259.html 说实话,完全理解题意了基本就是水题.但对我不是.

#include<bits/stdc++.h>
using namespace std;
int T;
char str[1000];
int main(){
    cin>>T;
    while(T--){
        int N,M;
        cin>>N>>M;
        int c=0,m=0,o=0,b=0;
        getchar();
        for(int i=0;i<N;++i){
            gets(str);
            if(str[0]=='C'){
                c++;
            }else if(str[0]=='M'){
                m++;
            }else if(str[0]=='O'){
                o++;
            }else if(str[0]=='B'){
                b++;
            }
        }
        int ans=o*(2+(N-1)+m*2)+b*(2+m*2);
        if(ans>=M){
            puts("Mrghllghghllghg!");
        }else puts("Tell you a joke, the execution of Paladin.");
    }
    return 0;
}

K:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=5010;
int N;
stack<char> st;
int main(){
    while(~scanf("%d\n",&N)){
        char qb;
        while(N--){
            int f=0;
            do{
                do{
                    qb=getchar();
                    if(isalpha(qb)) st.push(qb);
                }while(qb!=' ' && qb!='\n');
                if(f==0)f++;
                else printf(" ");
                while(!st.empty()){
                    printf("%c",st.top());
                    st.pop();
                }
            }while(qb!='\n');
            printf("\n");
        }
    }
    return 0;
}