Advertisement
Guest User

Untitled

a guest
Apr 4th, 2018
264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MaxN = (int)1e6 + 10;
  6. const int INF = 1e9;
  7.  
  8. int n, a[MaxN], d[MaxN];
  9. long long s[MaxN];
  10. int cnt[MaxN], pr[MaxN];
  11.  
  12.  
  13. void solve() {
  14. scanf("%d", &n);
  15. for (int i = 1; i <= n; ++i) {
  16. scanf("%d", &a[i]);
  17. s[i] = a[i] + s[i - 1];
  18. }
  19. memset(cnt, 0, (n + 10) * sizeof(cnt[0]));
  20. for (int i = 1; i <= n; ++i) {
  21. long long num = s[i];
  22. long long den = s[n];
  23. long long g = __gcd(num, den);
  24. num /= g;
  25. den /= g;
  26. if (den <= n) {
  27. cnt[den] += 1;
  28. }
  29. }
  30. int ans = 0;
  31. for (int i = n; i >= 1; --i) {
  32. for (int j = i + i; j <= n; j += i) {
  33. cnt[j] += cnt[i];
  34. }
  35. }
  36. for (int i = 1; i <= n; ++i) {
  37. ans += cnt[i] == i;
  38. if (cnt[i] == i) {
  39. printf("1");
  40. } else {
  41. printf("0");
  42. }
  43. }
  44. printf("\n");
  45. }
  46.  
  47. int main() {
  48. // freopen("input.txt", "r", stdin);
  49. int t = 1000;
  50. scanf("%d", &t);
  51. while (t --> 0) {
  52. solve();
  53. }
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement