Influence on Social media – Problems – CodeChef
Problem
Recently social media has been flooded by fb posts, tweets, news articles about only thing – demonetization. A great debate is ongoing over it. Most of the people discussing in social media platform usually tend to take sides, i.e. either they support the move, or they not.
There is such a group ofN people, who vehemently discuss about their views about this everywhere possible on any platform. The influence of a person is determined by the number of posts he makes. The more posts you make about your support/opposition, more your influence. Usually it is hard to determine whether a person supports/opposes the moves just by reading their posts, as they will make some oblique references here and there, often followed by a big digression into cat- dog memes, and name calling as the final resort, sometimes as a first resort too in rare cases. But you came to know from FB AI team that the people whose support this move behave slightly oddly. Specifically, FB team told that a person will be a supporter if number of divisors of the number of posts a person makes is an odd prime number.
You are given information about number of posts each person makes, specifically person i makes Pi posts. A study about user behavior tells that no-one likes to have the same number of posts as the other persons as they consider it as a loss of their identity. So, users make posts in such a way that no two persons have the same number of posts, i.e., all thePi‘s are distinct. You want to study the social media strength of users supporting the move. Let K denote the number of supporters of the move. For each i-th most influential supporter , you want to find his/her rank in overall influence in the social media (considering both supporters/opposers).
Input
The first line contains an integer T denoting the number of test cases. T test cases follow.
The first line of each test case contains a single integer N denoting the number of people in the group on social media.
The second line of each test case contains N space separated integers Pi denoting the number of posts made by i-th person.
Output
For each test case, output a single line containing K space separated integers, where i-th of them denotes the overall influence rank of i– th most influential supporter. If K is zero, output “No supporter found.” (without quotes) instead.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 105
- 1 ≤ Pi ≤ 1012
- Sum of N over all test cases ≤ 105
Example
<strong>Input:</strong> 2 2 1 3 2 13 9
Output: No supporter found. 2
Explanation
Example case 1. There are two persons on the social media group. You can see that first person has made 1 post. As, number of divisors of 1 are 1, which is odd but not a prime, so first person is an opponent of demonetization move. Second person is also opponent of the move, as number of divisors of 3 are 2 (1 and 3), which is even.
As there is no supporter, so the output should be “No supporter found.”.
Example case 2. Number of divisors of 13 are 2, which are even. So, person 1 is an opponent of the move. Number of divisors of 9 are 1, 3, 9, which is 3. As 3 is an odd and prime number, person 2 is a supporter of the move. Now, we want to find the overall influence ranking of person 2. We see that person 1 has higher number of posts than person 2. So, influence rank of person 2 will be 2.
Analysis:
Prime factor decomposition: N=p1^c1*p2^c2……pi^ci
Obviously: the number of factors of N is: (c1 + 1)*(c2 + 1)…(ci + 1);
So we only need to determine whether the product (c1 + 1) * (c2 + 1)… (ci + 1) is a prime number. And because a prime number cannot be the product of multiple numbers, if N wants to meet the meaning of the question, This can only be factored by a prime number;
That is: N=p1^c1, and c1 + 1 is a prime number
You can first use a prime number sieve to sift out the prime numbers in the 1e6 range.
Here, if we directly use traversal to decompose the numbers in each sequence after preprocessing, it will take a lot of time;
Note that pi<=1e12, and the smallest prime number 2^63 has far exceeded 1e12, so we will first find the c power of all prime numbers. A prime only needs to be required at most 63 times, where c is a prime number. , then we only need to match pi.
This prints out the running time of the program and takes a look: vs2019 gets the code running time (gets the time difference ms)_vs2019 function running time-CSDN Blog
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 1e6 + 5;
int n;
LL p[N];
int an[M];
vector<int>prime;
void init() {
an[1] = 1;
for (int i = 2; i < M; i + + ) {
if (an[i] == 0)
prime.push_back(i);
for (int j = 0; j < prime.size() & amp; & amp; prime[j] * i < M; j + + ) {
an[prime[j] * i] = 1;
}
}
}
int cmp(const LL & amp; a, const LL & amp; b) {
return a > b;
}
unordered_map<LL, int>mp;
void init1() {
for (int i = 0; i < prime.size(); i + + ) {
LL t = prime[i];
for (int j = 3; j < 60; j + + ) {
t *= prime[i];
if (an[j])
continue;
if (t > 1e12)
break;
mp[t] = 1;
}
}
}
int main() {
int T;
cin >> T;
init();
init1();
while (T--) {
scanf("%d", & amp;n);
LL t;
for (int i = 1; i <= n; i + + ) {
scanf("%lld", & amp;p[i]);
}
sort(p + 1, p + 1 + n, cmp);
int flg = 0;
for (int i = 1; i <= n; i + + ) {
if (mp[p[i]]) {
flg = 1;
printf("%d ", i);
}
}
if (!flg)
printf("No supporter found.");
printf("\\
");
}
return 0;
}