长乐集训DAY12

Posted on By 吴, 吴玮航

上午
原题：见他人blog
T2 暴力20分，没什么好说的，直接上代码（不开long long 见祖宗）

#include
using namespace std;
long long int a,b,c,d,m,n;
int main()
{
    freopen("fib.in","r",stdin);
    freopen("fib.out","w",stdout);  
    cin>>a>>b>>m>>n;
    if(n==0||n==1)
    {
        cout<<"1"<<endl;
        return 0;
    }
    for(int i=2;i<=n;i++)
    {
        c=(a+b)+2*sqrt((3+a*b));
//      c%=(m*m);
        a=b;
        b=c;

//      cout<<i<<"    "<<c%m<<endl;
    }
    cout<<c%m<<endl;
}

下午
T2 赛时在freopen中把w打成了W喜提FE,赛后提交40分，TLE到起飞。然后赛后根据规律找出了一种优化算法（时间来不及了不作详解，见代码。）

找规律代码

#include<bits/stdc++.h>
using namespace std;
long long int t,n,ans;
int main()
{
//  freopen("treatment.in","r",stdin);
//  freopen("treatment.out","w",stdout);    
    cin>>t;
    for(int ii=1;ii<=t;ii++)
    {
        cin>>n;
        ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=n%i;
//          cout<<i<<"      "<<n%i<<"  "<<ans<<endl;
        }
        cout<<ans<<endl;
    }
}

优化代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long int 
int tt,n,now,t,nex,re,p;
int ans;
int sum(int nn,int xx,int tt)
{
    int a=n%nn;
    int b=tt*(nn-xx-1)+n%nn;
    int c=tt;
//  cout<<tt<<"  n%nn  ->  "<<n%nn<<"  --->   "<<(b-a+c)/c<<" "<<a<<" "<<b<<"    now/nex/tt  "<<now<<" "<<nex<<" "<<tt<<"  ans->  "<<(((a+b)*(b-a+c))/c)/2<<endl;
    return (((a+b)*(b-a+c))/c)/2;
}
signed main()
{
    freopen("treatment.in","r",stdin);
    freopen("treatment.out","w",stdout);    
    cin>>tt;
/*  while(1)
    {
        int x,y,z;
        cin>>x>>y>>z;
        cout<<sum(x,y,z)<<endl;
    }*/
    for(int ii=1;ii<=tt;ii++)
    {
        cin>>n;
        now=n;
        nex=n/2;
        t=1;
        ans=0;
        while(nex>1)
        {
            ans+=re=sum(now,nex,t);

            now=nex;
            t++;
//          cout<<" now%t  -->  "<<now%t<<" "<<re<<endl;
//          nex=(t*nex)/(t+1)+((t*nex)%(t+1))/t;
            if((now-(n%(now)))%(t+1)==0)
            {
                p=0;
            }
            else
            {
                p=1;
            }
            nex=now-(now-(n%(now)))/(t+1)-p;
        }
        int tz;
        if(n%2==0)
        {
            tz=0;
        }
        else
        {
            tz=1;
        }
        cout<<ans+tz<<endl;
    }
}

T3 暴力，谁都会，直接上代码。
代码

#include<bits/stdc++.h>
using namespace std;
int t[32000],l,r;
int s[1000005],poi;
bool v[10000005];
long long ans;
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>l>>r;
    for(int i=1;i<=sqrt(r)+2;i++)
    {
        t[i]=i*i;
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=2;j<=sqrt(i);j++)
        {
            if(i%t[j]==0)
            {
                poi++;
                s[poi]=i;
                v[i]=1;
                break;
            }
        }
    }
//  cout<<poi<<endl;
    for(int i=l;i<=r;i++)
    {
        if(v[i]==1)
        {
            for(int j=1;j<=poi;j++)
            {
                if(i%s[j]==0)
                {
                    ans++;
                }
            }
//          cout<<ans<<endl;
        }
    }
    cout<<ans<<endl;
}

小剧场
V

训练日志