fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb(x) push_back(x)
  3. #define all(x) x.begin(), x.end()
  4. #define N 1000005
  5. #define MOD 1000000007
  6. #define cout2(x, y) cout << x << " " << y << endl
  7.  
  8. using namespace std;
  9.  
  10.  
  11. int frec[N], dp[N];
  12. int a[N/10];
  13. int cta[N], t[N];
  14.  
  15. int main() {
  16.  
  17. 	int n, var = 2;
  18.  
  19. 	dp[1] = 1;
  20. 	for(int i = 2; i < N; i++){
  21.  
  22. 		dp[i] = 2 * dp[i - 1];
  23. 		if(dp[i] >= MOD)dp[i] %= MOD;
  24.  
  25.  
  26. 		dp[i] += var;
  27. 		if(dp[i] >= MOD)dp[i] %= MOD;
  28.  
  29. 		var *= 2;
  30. 		if(var >= MOD)var %= MOD;
  31. 	}
  32.  
  33. 	scanf("%d", &n);
  34. 	int maxi = 0;
  35.  
  36. 	for(int i = 0; i < n; i++){
  37.  
  38. 		scanf("%d", &a[i]);
  39. 		maxi = max(maxi, a[i]);
  40. 		cta[a[i]]++;
  41. 	}
  42.  
  43. 	long long ans = 0;
  44. 	for(long long i = 2; i <= maxi; i++){
  45.  
  46. 		long long total = 0;
  47. 		for(long long j = i; j <= maxi; j += i)total += cta[j];
  48. 		t[i] = total;	
  49. 	}
  50.  
  51. 	for(long long i = 2; i <= maxi; i++){
  52.  
  53. 		long long total = 0;
  54. 		ans += (i * dp[t[i]])%MOD;
  55.  
  56. 		for(long long j = i; j <= maxi; j += i){// n ->  j
  57.  
  58. 			if(t[j] > 0){
  59.  
  60. 				if(i != j){
  61. 					ans -= (i * dp[t[j]])%MOD;
  62. 					if(ans < 0)ans += MOD;
  63. 				}
  64. 			}
  65. 		}
  66. 	}
  67.  
  68.  
  69. 	printf("%I64d\n", ans);
  70. }
Success #stdin #stdout 0.01s 31248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
                                                               0
https://ideone.com/BG4EtW
Esto es un code
language:
C++14 (gcc 8.3)
created:
7 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!