今天也算写了点东西，没有偷懒，赶紧写一下今天坑了我一晚上的两个题，一会股市就要开盘了
BZOJ 2818: Gcd
其实这个题一开始五分钟我就把思路想的差不多了。。。
两个数的gcd为素数的意思就是这两个数除以某个素数后的gcd为1，很自然得想到了欧拉函数，然后立即把线性筛的板子贴过来了
我想把素数处理出来，后面基本是枚举素数吧
然后。。。我就跑偏了
我看数据范围1e7，时间给了十秒，结果我就在想可以把每个数跑一遍分别枚举素数递推。。。。
艹。。。其实直接枚举素数就行，反正每两个素数一定互素，所以不相互影响，用欧拉函数的前缀和就可以避免枚举每个素数。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const int N=1e7,M=1e9+7;
ll phi[N+10];
bool vis[N+10];
ll prime[N+10];
ll miu[N+10];
ll tot;
void init(){
miu[1]=1;
tot = 0;
for(ll i = 2; i <=N; i ++)
{
if(!vis[i])
{
prime[tot ++] = i;
phi[i] = i - 1;
miu[i]=-1;
}
for(ll j = 0; j < tot; j ++)
{
if(i * prime[j] >= N) break;
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
miu[i*prime[j]]=0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * phi[prime[j]];
miu[i*prime[j]]=-1*miu[i];
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n;
init();
cin>>n;
phi[1]=1;
for(int i=2;i<=n;i++)
{
phi[i]+=phi[i-1];
}
ll ans=0;
for(int i=0;i<=tot;i++)
{
int h=n/prime[i];
if(prime[i]>n)break;
ans+=phi[h]*2-1;
}
cout<<ans<<endl;
}
BZOJ 1452: [JSOI2009]Count
这个题一开始算了算复杂度，直接暴力明明不会超时啊，下面是我暴力结果超时的代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const int N=305,M=1e9+7;
int a[N][N];
int dp[N][N][N];
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int main()
{
//ios::sync_with_stdio(false);
int n,m;
//cin>>n>>m;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int q;
//cin>>q;
q=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int k=1;k<=100;k++)
{
dp[i][j][k]=dp[i][j-1][k]+dp[i-1][j][k]-dp[i-1][j-1][k];
}
dp[i][j][a[i][j]]++;
}
while(q--)
{
int flag;
//cin>>flag;
flag=read();
if(flag==1){
int x,y,c;
//cin>>x>>y>>c;
x=read(),y=read(),c=read();
for(int i=x;i<=n;i++)
for(int j=y;j<=m;j++){
dp[i][j][a[x][y]]--;
dp[i][j][c]++;
}
a[x][y]=c;
}
else {
int x1,x2,y1,y2,c;
//cin>>x1>>x2>>y1>>y2>>c;
x1=read(),x2=read(),y1=read(),y2=read(),c=read();
int ans=dp[x2][y2][c]-dp[x1-1][y2][c]-dp[x2][y1-1][c]+dp[x1-1][y1-1][c];
//cout<<ans<<endl;
printf("%d\n",ans);
}
}
}
怎么算十秒都应该可以跑出来啊。。。
然后我换上了树状数组，结果还是超时，经过半天的研究发现
我dp数组的第三维从100开到了300，导致交上去连测评都不给你测，直接报超时。。。艹
然后改过来，还是超时。。。
换成scanf和printf，还是超时。。。
终于换成读入挂过了。。。艹，垃圾测评机
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const int N=305,M=1e9+7;
int a[N][N];
int dp[N][N][105];
int lowbit(int x)
{
return x&(-x);
}
int n,m;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
void change(int x,int y,int c,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
dp[i][j][c]+=v;
}
int ask(int x,int y,int c)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=dp[i][j][c];
return ans;
}
int main()
{
//ios::sync_with_stdio(false);
//cin>>n>>m;
//scanf("%d%d",&n,&m);
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
//cin>>a[i][j];
//scanf("%d",&a[i][j]);
a[i][j]=read();
change(i,j,a[i][j],1);
}
int q;
//cin>>q;
//scanf("%d",&q);
q=read();
while(q--)
{
int flag;
//cin>>flag;
//scanf("%d",&flag);
flag=read();
if(flag==1){
int x,y,c;
//cin>>x>>y>>c;
//scanf("%d%d%d",&x,&y,&c);
x=read(),y=read(),c=read();
/*for(int i=x;i<=n;i++)
for(int j=y;j<=m;j++){
dp[i][j][a[x][y]]--;
dp[i][j][c]++;
}*/
change(x,y,a[x][y],-1);
change(x,y,c,1);
a[x][y]=c;
}
else {
int x1,x2,y1,y2,c;
//cin>>x1>>x2>>y1>>y2>>c;
//scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
x1=read(),x2=read(),y1=read(),y2=read(),c=read();
//int ans=dp[x2][y2][c]-dp[x1-1][y2][c]-dp[x2][y1-1][c]+dp[x1-1][y1-1][c];
int ans=ask(x2,y2,c)-ask(x1-1,y2,c)-ask(x2,y1-1,c)+ask(x1-1,y1-1,c);
printf("%d\n",ans);
}
}
}