fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int n,m,i,j,d,g,a[222222],N;
  7. long long nFi,nSe,fi,se,le,ri,mid;
  8. long long rF,rS,ret;
  9.  
  10. #define base 1000000000000000000LL
  11.  
  12. void check(int d){
  13. 	for(int i=2;i<=m;i++)if((a[i]-a[i-1])%d!=0)return;
  14. 	fi=(a[1]-1)/d;se=(n-a[m])/d;
  15. 	ret+=(fi+1)*(se+1);
  16. }
  17.  
  18. int main(){
  19. 	freopen("trees.in","r",stdin);
  20. 	freopen("trees.out","w",stdout);
  21. 	scanf("%d%d",&n,&m);
  22. 	for(i=1;i<=m;i++)scanf("%d",&a[i]);
  23. 	sort(a+1,a+m+1);
  24. 	if(m>1){
  25. 		g=a[2]-a[1];
  26. 		for(i=2;i<=m;i++)g=__gcd(g,a[i]-a[i-1]);
  27. 		for(i=1;i*i<=g;i++)if(g%i==0){
  28. 			check(i);
  29. 			if(g/i!=i)check(g/i);
  30. 		}
  31. 		cout<<ret<<endl;
  32. 	}else{
  33. 		i=1;N=max(a[1]-1,n-a[1]);
  34. 		while(i<=N){
  35. 			nFi=(a[1]-1)/i;nSe=(n-a[1])/i;
  36. 			le=i;ri=n;
  37. 			while(le<ri){
  38. 				mid=(le+ri+1)/2;
  39. 				if((((a[1]-1)/mid)!=nFi)||(((n-a[1])/mid)!=nSe))ri=mid-1;else le=mid;
  40. 			}
  41. 			rF+=(long long)(le-i+1)*(nFi+1)*(nSe+1);
  42. 			i=le+1;
  43. 		}
  44. 		cout<<rF-(N-1)<<endl;
  45. 	}
  46. 	return 0;
  47. }
Success #stdin #stdout 0.01s 3592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rXpAV
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!