首页 > 代码库 > 题解#1
题解#1
表示感觉一题开一篇博文好麻烦啊。。。于是写到一块算了。。。写多了再新开博文
现在做了几题：
2
【BZOJ3529: [Sdoi2014]数表】
定义f[i]为i的约数之和，g[i]为n，m内gcd=i的数对的个数。那么答案=sigma f[i]*g[i]。
变换一下发现可以把n，m提出来，变成ans=[n/i]*[m/i]*f[j]*mu[i/j] 其中j|i
可以把g[i]定义成一个新函数=f[j]*mu[i/j]
但我们发现计算的时候有a的限制，所以考虑离线操作，将询问按a排序，f[i]也从小到大排序。
但这样g[i]的值是一直发生改变的。所以我们需要用树状数组来进行单点修改和区间和查询。
1 struct rec{int x,y,z,id;}a[maxn]; 2 pa b[maxn]; 3 int mm,ret[maxn],mx,s[maxn],tot,p[maxn],mu[maxn],f[maxn]; 4 bool v[maxn]; 5 void get() 6 { 7 mu[1]=1; 8 for2(i,2,mx) 9 {10 if(!v[i])p[++tot]=i,mu[i]=-1;11 for1(j,tot)12 {13 int k=i*p[j];14 if(k>mx)break;15 v[k]=1;16 if(i%p[j])mu[k]=-mu[i];17 else {mu[k]=0;break;}18 }19 }20 for1(i,mx)21 for(int j=i;j<=mx;j+=i)22 f[j]+=i;23 for1(i,mx)b[i]=make_pair(f[i],i);24 sort(b+1,b+mx+1);25 }26 inline void add(int x,int y){if(!y)return;for(;x<=mx;x+=x&(-x))s[x]+=y;}27 inline int sum(int x){int t=0;for(;x;x-=x&(-x))t+=s[x];return t;}28 inline bool cmp(rec a,rec b){return a.z<b.z;}29 30 int main()31 32 {33 34 freopen("input.txt","r",stdin);35 36 freopen("output.txt","w",stdout);37 38 mm=read();39 for1(i,mm)a[i].x=read(),a[i].y=read(),a[i].z=read(),a[i].id=i,mx=max(mx,max(a[i].x,a[i].y));40 get();41 sort(a+1,a+mm+1,cmp);42 int l=0;43 for1(k,mm)44 {45 int r=upper_bound(b+1,b+mx+1,make_pair(a[k].z+1,-1))-b-1;46 for2(i,l+1,r)47 for(int j=b[i].second;j<=mx;j+=b[i].second)48 add(j,b[i].first*mu[j/b[i].second]);49 int n=a[k].x,m=a[k].y,ans=0;50 if(n>m)swap(n,m);51 for(int i=1,j;i<=n;i=j+1)52 {53 j=min(n/(n/i),m/(m/i));54 ans+=(n/i)*(m/i)*(sum(j)-sum(i-1));55 }56 ret[a[k].id]=ans;57 l=r;58 }59 for1(i,mm)printf("%d\n",ret[i]&2147483647);60 61 return 0;62 63 }
【BZOJ3239: Discrete Logging】
p是素数，裸BSGS。偷懒用了map。hash感觉写起来好麻烦。
1 map<int,int>mp; 2 inline int power(int x,int y,int p) 3 { 4 int t=1; 5 for(;y;y>>=1,x=(ll)x*x%p) 6 if(y&1)t=(ll)t*x%p; 7 return t; 8 } 9 10 int main()11 12 {13 14 freopen("input.txt","r",stdin);15 16 freopen("output.txt","w",stdout);17 int a,b,p,ans;18 19 while(scanf("%d%d%d",&p,&a,&b)!=EOF)20 {21 a%=p;b%=p;22 if(!a&&!b)ans=1;23 else if(!a)ans=-1;24 else 25 {26 ans=-1;27 int m=sqrt(p),t=1;28 mp.clear();29 mp[1]=m;30 for1(i,m-1)31 {32 t=(ll)t*a%p;33 if(!mp[t])mp[t]=i;34 }35 t=(ll)t*a%p;36 t=power(t,p-2,p);37 for0(i,p/m)38 {39 int j=mp[b];40 if(j){ans=j%m+i*m;break;}41 b=(ll)b*t%p;42 }43 }44 if(ans==-1)printf("no solution\n");else printf("%d\n",ans);45 }46 47 return 0;48 49 }
题解#1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。