fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty